Spell comparison_fn_t uniformly.
[kopensolaris-gnu/glibc.git] / manual / search.texi
1 @node Searching and Sorting
2 @chapter Searching and Sorting 
3
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.
8
9 @menu
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.
16 @end menu
17
18 @node Comparison Functions
19 @section Defining the Comparison Function
20 @cindex Comparison Function
21
22 In order to use the sorted array library functions, you have to describe
23 how to compare the elements of the array.
24
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''.
32
33 Here is an example of a comparison function which works with an array of
34 numbers of type @code{double}:
35
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
49
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.
53
54 @tindex comparison_fn_t
55 @example
56 int comparison_fn_t (const void *, const void *);
57 @end example
58
59 @node Array Search Function
60 @section Array Search Function
61 @cindex search function (for arrays)
62 @cindex binary search function (for arrays)
63 @cindex array search function
64
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
67 the header file @file{stdlib.h}.
68 @pindex stdlib.h
69
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}.
76
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.
83
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.
87
88 This function derives its name from the fact that it is implemented
89 using the binary search.
90 @end deftypefun
91
92 @node Array Sort Function
93 @section Array Sort Function
94 @cindex sort function (for arrays)
95 @cindex quick sort function (for arrays)
96 @cindex array sort function
97
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
102
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}.
108
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.
114
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.
121
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.
125
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}):
129
130 @example
131 @{
132   double *array;
133   int size;
134   @dots{}
135   qsort (array, size, sizeof (double), compare_doubles);
136 @}
137 @end example
138
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
142
143 @node Search/Sort Example
144 @section Searching and Sorting Example
145
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.
150
151 @comment This example is dedicated to the memory of Jim Henson.  RIP.
152 @example
153 #include <stdlib.h>
154 #include <stdio.h>
155 #include <string.h>
156
157 /* @r{Define an array of critters to sort.} */
158
159 struct critter @{
160   char *name;
161   char *species;
162   @};
163
164 /* @r{Initialize the array, but not properly sorted.}  */
165
166 struct critter muppets[]
167   = @{@{"Kermit", "frog"@},
168      @{"Piggy", "pig"@},
169      @{"Gonzo", "whatever"@},
170      @{"Fozzie", "bear"@},
171      @{"Sam", "eagle"@},
172      @{"Robin", "frog"@},
173      @{"Animal", "animal"@},
174      @{"Camilla", "chicken"@},
175      @{"Sweetums", "monster"@},
176      @{"Dr. Strangepork", "pig"@},
177      @{"Link Hogthrob", "pig"@},
178      @{"Zoot", "human"@},
179      @{"Dr. Bunsen Honeydew", "human"@},
180      @{"Beaker", "human"@},
181      @{"Swedish Chef", "human"@}@};
182
183 int count = sizeof(muppets) / sizeof(struct critter);
184
185 /* @r{This is the comparison function for sorting and searching.} */
186
187 int
188 critter_cmp (const struct critter *c1,
189              const struct critter *c2)
190 @{
191   return strcmp (c1->name, c2->name);
192 @}
193
194 /* @r{Print information about a critter.} */
195
196 void
197 print_critter (const struct critter *c)
198 @{
199   printf ("%s, the %s\n", c->name, c->species);
200 @}
201
202 /* @r{Do the lookup into the sorted array.} */
203
204 void
205 find_critter (char *name)
206 @{
207   struct critter target, *result;
208   target.name = name;
209   result = bsearch (&target, muppets, count,
210                     sizeof (struct critter),
211                     critter_cmp);
212   if (result)
213     print_critter (result);
214   else
215     printf ("Couldn't find %s.\n", name);
216 @}
217
218 /* @r{Main program.} */
219
220 void
221 main (void)
222 @{
223   int i;
224   
225   qsort (muppets, count,
226          sizeof (struct critter), critter_cmp);
227
228   for (i=0; i<count; i++)
229     print_critter (&muppets[i]);
230   printf ("\n");
231
232   find_critter ("Kermit");
233   find_critter ("Gonzo");
234   find_critter ("Janice");
235 @}  
236 @end example
237
238 @cindex Kermit the frog
239 The output from this program looks like:
240
241 @example
242 Animal, the animal
243 Beaker, the human
244 Camilla, the chicken
245 Dr. Bunsen Honeydew, the human
246 Dr. Strangepork, the pig
247 Fozzie, the bear
248 Gonzo, the whatever
249 Kermit, the frog
250 Link Hogthrob, the pig
251 Piggy, the pig
252 Robin, the frog
253 Sam, the eagle
254 Swedish Chef, the human
255 Sweetums, the monster
256 Zoot, the human
257
258
259 Kermit, the frog
260 Gonzo, the whatever
261 Couldn't find Janice.
262 @end example
263
264