1 @node Searching and Sorting, I/O Overview, 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 @tindex comparison_fn_t
56 @example
57 int comparison_fn_t (const void *, const void *);
58 @end example
60 @node Array Search Function, Array Sort Function, Comparison Functions, Searching and Sorting
61 @section Array Search Function
62 @cindex search function (for arrays)
63 @cindex binary search function (for arrays)
64 @cindex array search function
66 To search a sorted array for an element matching the key, use the
67 @code{bsearch} function.  The prototype for this function is in
69 @pindex stdlib.h
71 @comment stdlib.h
72 @comment ANSI
73 @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
74 The @code{bsearch} function searches the sorted array @var{array} for an object
75 that is equivalent to @var{key}.  The array contains @var{count} elements,
76 each of which is of size @var{size}.
78 The @var{compare} function is used to perform the comparison.  This
79 function is called with two pointer arguments and should return an
80 integer less than, equal to, or greater than zero corresponding to
81 whether its first argument is considered less than, equal to, or greater
82 than its second argument.  The elements of the @var{array} must already
83 be sorted in ascending order according to this comparison function.
85 The return value is a pointer to the matching array element, or a null
86 pointer if no match is found.  If the array contains more than one element
87 that matches, the one that is returned is unspecified.
89 This function derives its name from the fact that it is implemented
90 using the binary search.
91 @end deftypefun
93 @node Array Sort Function, Search/Sort Example, Array Search Function, Searching and Sorting
94 @section Array Sort Function
95 @cindex sort function (for arrays)
96 @cindex quick sort function (for arrays)
97 @cindex array sort function
99 To sort an array using an arbitrary comparison function, use the
100 @code{qsort} function.  The prototype for this function is in
101 @file{stdlib.h}.
102 @pindex stdlib.h
104 @comment stdlib.h
105 @comment ANSI
106 @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
107 The @var{qsort} function sorts the array @var{array}.  The array contains
108 @var{count} elements, each of which is of size @var{size}.
110 The @var{compare} function is used to compare perform the comparison on
111 the array elements.  This function is called with two pointer arguments
112 and should return an integer less than, equal to, or greater than zero
113 corresponding to whether its first argument is considered less than,
114 equal to, or greater than its second argument.
116 @cindex stable sorting
117 @strong{Warning:} if two objects compare as equal, their order after
118 sorting is unpredictable.  That is to say, the sorting is not stable.
119 This can make a difference when the comparison considers only part of
120 the elements.  Two elements with the same sort key may differ in other
121 respects.
123 If you want the effect of a stable sort, you can get this result by
124 writing the comparison function so that, lacking other reason
125 distinguish between two elements, it compares them by their addresses.
127 Here is a simple example of sorting an array of doubles in numerical
128 order, using the comparison function defined above (@pxref{Comparison
129 Functions}):
131 @example
132 @{
133   double *array;
134   int size;
135   @dots{}
136   qsort (array, size, sizeof (double), compare_doubles);
137 @}
138 @end example
140 The @code{qsort} function derives its name from the fact that it was
141 originally implemented using the algorithm ``quick sort''.
142 @end deftypefun
144 @node Search/Sort Example,  , Array Sort Function, Searching and Sorting
145 @section Searching and Sorting Example
147 Here is an example showing the use of @code{qsort} and @code{bsearch}
148 with an array of structures.  The objects in the array are sorted
149 by comparing their @code{name} fields with the @code{strcmp} function.
150 Then, we can look up individual objects based on their names.
152 @comment This example is dedicated to the memory of Jim Henson.  RIP.
153 @example
154 @include search.c.texi
155 @end example
157 @cindex Kermit the frog
158 The output from this program looks like:
160 @example
161 Animal, the animal
162 Beaker, the human
163 Camilla, the chicken
164 Dr. Bunsen Honeydew, the human
165 Dr. Strangepork, the pig
166 Fozzie, the bear
167 Gonzo, the whatever
168 Kermit, the frog