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