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