Many changes after first published edition and comments from mib; still not finished.
[kopensolaris-gnu/glibc.git] / manual / search.texi
1 @node Searching and Sorting, Pattern Matching, Locales, Top
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
12                                  are general, you have to specify the
13                                  ordering. 
14 * Array Search Function::       The @code{bsearch} function.
15 * Array Sort Function::         The @code{qsort} function.
16 * Search/Sort Example::         An example program.
17 @end menu
18
19 @node Comparison Functions, Array Search Function,  , Searching and Sorting
20 @section Defining the Comparison Function
21 @cindex Comparison Function
22
23 In order to use the sorted array library functions, you have to describe
24 how to compare the elements of the array.
25
26 To do this, you supply a comparison function to compare two elements of
27 the array.  The library will call this function, passing as arguments
28 pointers to two array elements to be compared.  Your comparison function
29 should return a value the way @code{strcmp} (@pxref{String/Array
30 Comparison}) does: negative if the first argument is ``less'' than the
31 second, zero if they are ``equal'', and positive if the first argument
32 is ``greater''.
33
34 Here is an example of a comparison function which works with an array of
35 numbers of type @code{double}:
36
37 @smallexample
38 int
39 compare_doubles (const double *a, const double *b)
40 @{
41   return (int) (*a - *b);
42 @}
43 @end smallexample
44
45 The header file @file{stdlib.h} defines a name for the data type of
46 comparison functions.  This type is a GNU extension.
47
48 @comment stdlib.h
49 @comment GNU
50 @tindex comparison_fn_t
51 @smallexample
52 int comparison_fn_t (const void *, const void *);
53 @end smallexample
54
55 @node Array Search Function, Array Sort Function, Comparison Functions, Searching and Sorting
56 @section Array Search Function
57 @cindex search function (for arrays)
58 @cindex binary search function (for arrays)
59 @cindex array search function
60
61 To search a sorted array for an element matching the key, use the
62 @code{bsearch} function.  The prototype for this function is in
63 the header file @file{stdlib.h}.
64 @pindex stdlib.h
65
66 @comment stdlib.h
67 @comment ANSI
68 @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
69 The @code{bsearch} function searches the sorted array @var{array} for an object
70 that is equivalent to @var{key}.  The array contains @var{count} elements,
71 each of which is of size @var{size} bytes.  
72
73 The @var{compare} function is used to perform the comparison.  This
74 function is called with two pointer arguments and should return an
75 integer less than, equal to, or greater than zero corresponding to
76 whether its first argument is considered less than, equal to, or greater
77 than its second argument.  The elements of the @var{array} must already
78 be sorted in ascending order according to this comparison function.
79
80 The return value is a pointer to the matching array element, or a null
81 pointer if no match is found.  If the array contains more than one element
82 that matches, the one that is returned is unspecified.
83
84 This function derives its name from the fact that it is implemented
85 using the binary search algorithm.
86 @end deftypefun
87
88 @node Array Sort Function, Search/Sort Example, Array Search Function, Searching and Sorting
89 @section Array Sort Function
90 @cindex sort function (for arrays)
91 @cindex quick sort function (for arrays)
92 @cindex array sort function
93
94 To sort an array using an arbitrary comparison function, use the
95 @code{qsort} function.  The prototype for this function is in
96 @file{stdlib.h}.
97 @pindex stdlib.h
98
99 @comment stdlib.h
100 @comment ANSI
101 @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
102 The @var{qsort} function sorts the array @var{array}.  The array contains
103 @var{count} elements, each of which is of size @var{size}.
104
105 The @var{compare} function is used to perform the comparison on the
106 array elements.  This function is called with two pointer arguments and
107 should return an integer less than, equal to, or greater than zero
108 corresponding to whether its first argument is considered less than,
109 equal to, or greater than its second argument.
110
111 @cindex stable sorting
112 @strong{Warning:} If two objects compare as equal, their order after
113 sorting is unpredictable.  That is to say, the sorting is not stable.
114 This can make a difference when the comparison considers only part of
115 the elements.  Two elements with the same sort key may differ in other
116 respects.
117
118 If you want the effect of a stable sort, you can get this result by
119 writing the comparison function so that, lacking other reason
120 distinguish between two elements, it compares them by their addresses.
121
122 Here is a simple example of sorting an array of doubles in numerical
123 order, using the comparison function defined above (@pxref{Comparison
124 Functions}):
125
126 @smallexample
127 @{
128   double *array;
129   int size;
130   @dots{}
131   qsort (array, size, sizeof (double), compare_doubles);
132 @}
133 @end smallexample
134
135 The @code{qsort} function derives its name from the fact that it was
136 originally implemented using the ``quick sort'' algorithm.
137 @end deftypefun
138
139 @node Search/Sort Example,  , Array Sort Function, Searching and Sorting
140 @section Searching and Sorting Example
141
142 Here is an example showing the use of @code{qsort} and @code{bsearch}
143 with an array of structures.  The objects in the array are sorted
144 by comparing their @code{name} fields with the @code{strcmp} function.
145 Then, we can look up individual objects based on their names.
146
147 @comment This example is dedicated to the memory of Jim Henson.  RIP.
148 @smallexample
149 @include search.c.texi
150 @end smallexample
151
152 @cindex Kermit the frog
153 The output from this program looks like:
154
155 @smallexample
156 Kermit, the frog
157 Piggy, the pig
158 Gonzo, the whatever
159 Fozzie, the bear
160 Sam, the eagle
161 Robin, the frog
162 Animal, the animal
163 Camilla, the chicken
164 Sweetums, the monster
165 Dr. Strangepork, the pig
166 Link Hogthrob, the pig
167 Zoot, the human
168 Dr. Bunsen Honeydew, the human
169 Beaker, the human
170 Swedish Chef, the human
171
172 Animal, the animal
173 Beaker, the human
174 Camilla, the chicken
175 Dr. Bunsen Honeydew, the human
176 Dr. Strangepork, the pig
177 Fozzie, the bear
178 Gonzo, the whatever
179 Kermit, the frog
180 Link Hogthrob, the pig
181 Piggy, the pig
182 Robin, the frog
183 Sam, the eagle
184 Swedish Chef, the human
185 Sweetums, the monster
186 Zoot, the human
187
188 Kermit, the frog
189 Gonzo, the whatever
190 Couldn't find Janice.
191 @end smallexample
192
193