Fixed some formatting and indexing problems.
[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.  The return value from the comparison
8 function should follow the same conventions as the @code{strcmp}
9 function; @pxref{String/Array Comparison}.
10
11 @menu
12 * Array Search Function::               The @code{bsearch} function.
13 * Array Sort Function::                 The @code{qsort} function.
14 * Searching and Sorting Example::       An example program.
15 @end menu
16
17 @node Array Search Function
18 @section Array Search Function
19
20 To search a sorted array for an element matching the key, use the
21 @code{bsearch} function.  The prototype for this function is in
22 the header file @file{stdlib.h}.
23 @pindex stdlib.h
24
25 @comment stdlib.h
26 @comment ANSI
27 @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, int (*@var{compare}) (const void *, const void *))
28 The @code{bsearch} function searches the sorted array @var{array} for an object
29 that is equivalent to @var{key}.  The array contains @var{count} elements,
30 each of which is of size @var{size}.
31
32 The @var{compare} function is used to perform the comparison.  This
33 function is called with two pointer arguments and should return an
34 integer less than, equal to, or greater than zero corresponding to
35 whether its first argument is considered less than, equal to, or greater
36 than its second argument.  The elements of the @var{array} must already
37 be sorted in ascending order according to this comparison function.
38
39 The return value is a pointer to the matching array element, or a null
40 pointer if no match is found.  If the array contains more than one element
41 that matches, the one that is returned is unspecified.
42
43 Although the specific algorithm used by this function is not specified,
44 traditionally a binary search algorithm has been used; hence the name of
45 the function.
46 @end deftypefun
47
48 @node Array Sort Function
49 @section Array Sort Function
50
51 To sort an array using an arbitrary comparison function, use the
52 @code{qsort} function.  The prototype for this function is in
53 @file{stdlib.h}.
54 @pindex stdlib.h
55
56 @comment stdlib.h
57 @comment ANSI
58 @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, int (*@var{compare}) (const void *, const void *))
59 The @var{qsort} function sorts the array @var{array}.  The array contains
60 @var{count} elements, each of which is of size @var{size}.
61
62 The @var{compare} function is used to compare perform the comparison on
63 the array elements.  This function is called with two pointer arguments
64 and should return an integer less than, equal to, or greater than zero
65 corresponding to whether its first argument is considered less than,
66 equal to, or greater than its second argument.  If two objects compare
67 as equal, their order in the sorted array is unspecified.
68
69 Although the specific algorithm used by this function is not specified,
70 traditionally a quick sort algorithm has been used; hence the name of
71 the function.
72 @end deftypefun
73
74
75 @node Searching and Sorting Example
76 @section Searching and Sorting Example
77
78 Here is an example showing the use of @code{qsort} and @code{bsearch}
79 with an array of @code{struct}s.  The objects in the array are sorted
80 by comparing their @code{name} fields with the @code{strcmp} function.
81 Then, we can look up individual objects based on their names.
82
83 @comment This example is dedicated to the memory of Jim Henson.  RIP.
84 @example
85 #include <stdlib.h>
86 #include <stdio.h>
87 #include <string.h>
88
89 /* @r{Define an array of critters to sort.} */
90
91 struct critter @{
92   char *name;
93   char *species;
94   @};
95
96 struct critter muppets[] = @{@{"Kermit", "frog"@},
97                             @{"Piggy", "pig"@},
98                             @{"Gonzo", "whatever"@},
99                             @{"Fozzie", "bear"@},
100                             @{"Sam", "eagle"@},
101                             @{"Robin", "frog"@},
102                             @{"Animal", "animal"@},
103                             @{"Camilla", "chicken"@},
104                             @{"Sweetums", "monster"@},
105                             @{"Dr. Strangepork", "pig"@},
106                             @{"Link Hogthrob", "pig"@},
107                             @{"Zoot", "human"@},
108                             @{"Dr. Bunsen Honeydew", "human"@},
109                             @{"Beaker", "human"@},
110                             @{"Swedish Chef", "human"@}@};
111
112 int count = sizeof(muppets) / sizeof(struct critter);
113
114
115
116 /* @r{This is the comparison function used for sorting and searching.} */
117
118 int critter_cmp (const struct critter *c1, const struct critter *c2)
119 @{
120   return strcmp (c1->name, c2->name);
121 @}
122
123
124 /* @r{Print information about a critter.} */
125
126 void print_critter (const struct critter *c)
127 @{
128   printf ("%s, the %s\n", c->name, c->species);
129 @}
130
131
132 /* @r{Do the lookup into the sorted array.} */
133
134 void find_critter (char *name)
135 @{
136   struct critter target, *result;
137   target.name = name;
138   result = bsearch (&target, muppets, count, sizeof(struct critter),
139                     critter_cmp);
140   if (result)
141     print_critter (result);
142   else
143     printf ("Couldn't find %s.\n", name);
144 @}
145
146
147 /* @r{Main program.} */
148
149 void main (void)
150 @{
151   int i;
152   
153   qsort (muppets, count, sizeof(struct critter), critter_cmp);
154
155   for (i=0; i<count; i++)
156     print_critter (&muppets[i]);
157   printf ("\n");
158
159   find_critter ("Kermit");
160   find_critter ("Gonzo");
161   find_critter ("Janice");
162 @}  
163 @end example
164
165 The output from this program looks like:
166
167 @example
168 Animal, the animal
169 Beaker, the human
170 Camilla, the chicken
171 Dr. Bunsen Honeydew, the human
172 Dr. Strangepork, the pig
173 Fozzie, the bear
174 Gonzo, the whatever
175 Kermit, the frog
176 Link Hogthrob, the pig
177 Piggy, the pig
178 Robin, the frog
179 Sam, the eagle
180 Swedish Chef, the human
181 Sweetums, the monster
182 Zoot, the human
183
184
185 Kermit, the frog
186 Gonzo, the whatever
187 Couldn't find Janice.
188 @end example
189
190