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