miscellaneous edits
[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 * Array Search Function::               The @code{bsearch} function.
11 * Array Sort Function::                 The @code{qsort} function.
12 * Searching and Sorting Example::       An example program.
13 @end menu
14
15 @node Comparison Functions
16 @section Defining the Comparison Function
17 @cindex Comparison Function
18
19 In order to use the sorted array library functions, you have to describe
20 how to compare the elements of the array.
21
22 To do this, you supply a comparison function to compare two elements of
23 the array.  The library will call this function, passing as arguments
24 pointers to two array elements to be compared.  Your comparison function
25 should return a value the way @code{strcmp} (@pxref{String/Array
26 Comparison}) does: negative if the first argument is ``less'' than the
27 second, zero if they are ``equal'', and positive if the first argument
28 is ``greater''.
29
30 Here is an example of a comparison function which works with an array of
31 numbers of type @code{double}:
32
33 @example
34 int
35 compare_doubles (const double *a, const double *b)
36 @{
37   double temp = *a - *b;
38   if (temp > 0)
39     return 1;
40   else if (temp < 0)
41     return -1;
42   else
43     return 0;
44 @}
45 @end example
46
47 The header file @file{stdlib.h} defines a name for the data type of
48 comparison functions.  This is a GNU extension and thus defined only if
49 you request the GNU extensions.
50
51 @tindex comparison_fn_t
52 @example
53 int comparison_fn_t (const void *, const void *);
54 @end example
55
56 @node Array Search Function
57 @section Array Search Function
58 @cindex search function (for arrays)
59 @cindex binary search function (for arrays)
60 @cindex array search function
61
62 To search a sorted array for an element matching the key, use the
63 @code{bsearch} function.  The prototype for this function is in
64 the header file @file{stdlib.h}.
65 @pindex stdlib.h
66
67 @comment stdlib.h
68 @comment ANSI
69 @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, compare_fn_t @var{compare})
70 The @code{bsearch} function searches the sorted array @var{array} for an object
71 that is equivalent to @var{key}.  The array contains @var{count} elements,
72 each of which is of size @var{size}.
73
74 The @var{compare} function is used to perform the comparison.  This
75 function is called with two pointer arguments and should return an
76 integer less than, equal to, or greater than zero corresponding to
77 whether its first argument is considered less than, equal to, or greater
78 than its second argument.  The elements of the @var{array} must already
79 be sorted in ascending order according to this comparison function.
80
81 The return value is a pointer to the matching array element, or a null
82 pointer if no match is found.  If the array contains more than one element
83 that matches, the one that is returned is unspecified.
84
85 This function derives its name from the fact that it is implemented
86 using the binary search.
87 @end deftypefun
88
89 @node Array Sort Function
90 @section Array Sort Function
91 @cindex sort function (for arrays)
92 @cindex quick sort function (for arrays)
93 @cindex array sort function
94
95 To sort an array using an arbitrary comparison function, use the
96 @code{qsort} function.  The prototype for this function is in
97 @file{stdlib.h}.
98 @pindex stdlib.h
99
100 @comment stdlib.h
101 @comment ANSI
102 @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, compare_fn_t @var{compare})
103 The @var{qsort} function sorts the array @var{array}.  The array contains
104 @var{count} elements, each of which is of size @var{size}.
105
106 The @var{compare} function is used to compare perform the comparison on
107 the array elements.  This function is called with two pointer arguments
108 and should return an integer less than, equal to, or greater than zero
109 corresponding to whether its first argument is considered less than,
110 equal to, or greater than its second argument.
111
112 @cindex stable sorting
113 @strong{Warning:} if two objects compare as equal, their order after
114 sorting is unpredictable.  That is to say, the sorting is not stable.
115 This can make a difference when the comparison considers only part of
116 the elements.  Two elements with the same sort key may differ in other
117 respects.
118
119 If you want the effect of a stable sort, you can get this result by
120 writing the comparison function so that, lacking other reason
121 distinguish between two elements, it compares them by their addresses.
122
123 Here is a simple example of sorting an array of doubles in numerical
124 order, using the comparison function defined above (@pxref{Comparison
125 Functions}):
126
127 @example
128 @{
129   double *array;
130   int size;
131   @dots{}
132   qsort (array, size, sizeof (double), compare_doubles);
133 @}
134 @end example
135
136 The @code{qsort} function derives its name from the fact that it was
137 originally implemented using the algorithm ``quick sort''.
138 @end deftypefun
139
140
141 @node Searching and Sorting Example
142 @section Searching and Sorting Example
143
144 Here is an example showing the use of @code{qsort} and @code{bsearch}
145 with an array of structures.  The objects in the array are sorted
146 by comparing their @code{name} fields with the @code{strcmp} function.
147 Then, we can look up individual objects based on their names.
148
149 @comment This example is dedicated to the memory of Jim Henson.  RIP.
150 @example
151 #include <stdlib.h>
152 #include <stdio.h>
153 #include <string.h>
154
155 /* @r{Define an array of critters to sort.} */
156
157 struct critter @{
158   char *name;
159   char *species;
160   @};
161
162 /* @r{Initialize the array in an order which is not properly sorted.}  */
163
164 struct critter muppets[] = @{@{"Kermit", "frog"@},
165                             @{"Piggy", "pig"@},
166                             @{"Gonzo", "whatever"@},
167                             @{"Fozzie", "bear"@},
168                             @{"Sam", "eagle"@},
169                             @{"Robin", "frog"@},
170                             @{"Animal", "animal"@},
171                             @{"Camilla", "chicken"@},
172                             @{"Sweetums", "monster"@},
173                             @{"Dr. Strangepork", "pig"@},
174                             @{"Link Hogthrob", "pig"@},
175                             @{"Zoot", "human"@},
176                             @{"Dr. Bunsen Honeydew", "human"@},
177                             @{"Beaker", "human"@},
178                             @{"Swedish Chef", "human"@}@};
179
180 int count = sizeof(muppets) / sizeof(struct critter);
181
182 /* @r{This is the comparison function used for sorting and searching.} */
183
184 int
185 critter_cmp (const struct critter *c1, const struct critter *c2)
186 @{
187   return strcmp (c1->name, c2->name);
188 @}
189
190 /* @r{Print information about a critter.} */
191
192 void
193 print_critter (const struct critter *c)
194 @{
195   printf ("%s, the %s\n", c->name, c->species);
196 @}
197
198 /* @r{Do the lookup into the sorted array.} */
199
200 void
201 find_critter (char *name)
202 @{
203   struct critter target, *result;
204   target.name = name;
205   result = bsearch (&target, muppets, count, sizeof(struct critter),
206                     critter_cmp);
207   if (result)
208     print_critter (result);
209   else
210     printf ("Couldn't find %s.\n", name);
211 @}
212
213 /* @r{Main program.} */
214
215 void
216 main (void)
217 @{
218   int i;
219   
220   qsort (muppets, count, sizeof(struct critter), critter_cmp);
221
222   for (i=0; i<count; i++)
223     print_critter (&muppets[i]);
224   printf ("\n");
225
226   find_critter ("Kermit");
227   find_critter ("Gonzo");
228   find_critter ("Janice");
229 @}  
230 @end example
231
232 @cindex Kermit the frog
233 The output from this program looks like:
234
235 @example
236 Animal, the animal
237 Beaker, the human
238 Camilla, the chicken
239 Dr. Bunsen Honeydew, the human
240 Dr. Strangepork, the pig
241 Fozzie, the bear
242 Gonzo, the whatever
243 Kermit, the frog
244 Link Hogthrob, the pig
245 Piggy, the pig
246 Robin, the frog
247 Sam, the eagle
248 Swedish Chef, the human
249 Sweetums, the monster
250 Zoot, the human
251
252
253 Kermit, the frog
254 Gonzo, the whatever
255 Couldn't find Janice.
256 @end example
257
258