1 @node Searching and Sorting, Pattern Matching, Locales, Top
2 @chapter Searching and Sorting
4 This chapter describes functions for searching and sorting arrays of
5 arbitrary objects.  You pass the appropriate comparison function to be
6 applied as an argument, along with the size of the objects in the array
7 and the total number of elements.
10 * Comparison Functions::        Defining how to compare two objects.
11                                  Since the sort and search facilities
12                                  are general, you have to specify the
13                                  ordering.
14 * Array Search Function::       The @code{bsearch} function.
15 * Array Sort Function::         The @code{qsort} function.
16 * Search/Sort Example::         An example program.
19 @node Comparison Functions, Array Search Function,  , Searching and Sorting
20 @section Defining the Comparison Function
21 @cindex Comparison Function
23 In order to use the sorted array library functions, you have to describe
24 how to compare the elements of the array.
26 To do this, you supply a comparison function to compare two elements of
27 the array.  The library will call this function, passing as arguments
28 pointers to two array elements to be compared.  Your comparison function
29 should return a value the way @code{strcmp} (@pxref{String/Array
30 Comparison}) does: negative if the first argument is ``less'' than the
31 second, zero if they are ``equal'', and positive if the first argument
32 is ``greater''.
34 Here is an example of a comparison function which works with an array of
35 numbers of type @code{double}:
37 @example
38 int
39 compare_doubles (const double *a, const double *b)
40 @{
41   double temp = *a - *b;
42   if (temp > 0)
43     return 1;
44   else if (temp < 0)
45     return -1;
46   else
47     return 0;
48 @}
49 @end example
51 The header file @file{stdlib.h} defines a name for the data type of
52 comparison functions.  This is a GNU extension and thus defined only if
53 you request the GNU extensions.
55 @comment stdlib.h
56 @comment GNU
57 @tindex comparison_fn_t
58 @example
59 int comparison_fn_t (const void *, const void *);
60 @end example
62 @node Array Search Function, Array Sort Function, Comparison Functions, Searching and Sorting
63 @section Array Search Function
64 @cindex search function (for arrays)
65 @cindex binary search function (for arrays)
66 @cindex array search function
68 To search a sorted array for an element matching the key, use the
69 @code{bsearch} function.  The prototype for this function is in
71 @pindex stdlib.h
73 @comment stdlib.h
74 @comment ANSI
75 @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
76 The @code{bsearch} function searches the sorted array @var{array} for an object
77 that is equivalent to @var{key}.  The array contains @var{count} elements,
78 each of which is of size @var{size}.
80 The @var{compare} function is used to perform the comparison.  This
81 function is called with two pointer arguments and should return an
82 integer less than, equal to, or greater than zero corresponding to
83 whether its first argument is considered less than, equal to, or greater
84 than its second argument.  The elements of the @var{array} must already
85 be sorted in ascending order according to this comparison function.
87 The return value is a pointer to the matching array element, or a null
88 pointer if no match is found.  If the array contains more than one element
89 that matches, the one that is returned is unspecified.
91 This function derives its name from the fact that it is implemented
92 using the binary search algorithm.
93 @end deftypefun
95 @node Array Sort Function, Search/Sort Example, Array Search Function, Searching and Sorting
96 @section Array Sort Function
97 @cindex sort function (for arrays)
98 @cindex quick sort function (for arrays)
99 @cindex array sort function
101 To sort an array using an arbitrary comparison function, use the
102 @code{qsort} function.  The prototype for this function is in
103 @file{stdlib.h}.
104 @pindex stdlib.h
106 @comment stdlib.h
107 @comment ANSI
108 @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
109 The @var{qsort} function sorts the array @var{array}.  The array contains
110 @var{count} elements, each of which is of size @var{size}.
112 The @var{compare} function is used to perform the comparison on the
113 array elements.  This function is called with two pointer arguments and
114 should return an integer less than, equal to, or greater than zero
115 corresponding to whether its first argument is considered less than,
116 equal to, or greater than its second argument.
118 @cindex stable sorting
119 @strong{Warning:} If two objects compare as equal, their order after
120 sorting is unpredictable.  That is to say, the sorting is not stable.
121 This can make a difference when the comparison considers only part of
122 the elements.  Two elements with the same sort key may differ in other
123 respects.
125 If you want the effect of a stable sort, you can get this result by
126 writing the comparison function so that, lacking other reason
127 distinguish between two elements, it compares them by their addresses.
129 Here is a simple example of sorting an array of doubles in numerical
130 order, using the comparison function defined above (@pxref{Comparison
131 Functions}):
133 @example
134 @{
135   double *array;
136   int size;
137   @dots{}
138   qsort (array, size, sizeof (double), compare_doubles);
139 @}
140 @end example
142 The @code{qsort} function derives its name from the fact that it was
143 originally implemented using the algorithm ``quick sort''.
144 @end deftypefun
146 @node Search/Sort Example,  , Array Sort Function, Searching and Sorting
147 @section Searching and Sorting Example
149 Here is an example showing the use of @code{qsort} and @code{bsearch}
150 with an array of structures.  The objects in the array are sorted
151 by comparing their @code{name} fields with the @code{strcmp} function.
152 Then, we can look up individual objects based on their names.
154 @comment This example is dedicated to the memory of Jim Henson.  RIP.
155 @example
156 @include search.c.texi
157 @end example
159 @cindex Kermit the frog
160 The output from this program looks like:
162 @example
163 Animal, the animal
164 Beaker, the human
165 Camilla, the chicken
166 Dr. Bunsen Honeydew, the human
167 Dr. Strangepork, the pig
168 Fozzie, the bear
169 Gonzo, the whatever
170 Kermit, the frog