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 ISO
  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 ISO
 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 Note that doing this may make the sorting algorithm less efficient, so
 122 do it only if necessary.
 123
 124 Here is a simple example of sorting an array of doubles in numerical
 125 order, using the comparison function defined above (@pxref{Comparison
 126 Functions}):
 127
 128 @smallexample
 129 @{
 130   double *array;
 131   int size;
 132   @dots{}
 133   qsort (array, size, sizeof (double), compare_doubles);
 134 @}
 135 @end smallexample
 136
 137 The @code{qsort} function derives its name from the fact that it was
 138 originally implemented using the ``quick sort'' algorithm.
 139 @end deftypefun
 140
 141 @node Search/Sort Example,  , Array Sort Function, Searching and Sorting
 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 @smallexample
 151 @include search.c.texi
 152 @end smallexample
 153
 154 @cindex Kermit the frog
 155 The output from this program looks like:
 156
 157 @smallexample
 158 Kermit, the frog
 159 Piggy, the pig
 160 Gonzo, the whatever
 161 Fozzie, the bear
 162 Sam, the eagle
 163 Robin, the frog
 164 Animal, the animal
 165 Camilla, the chicken
 166 Sweetums, the monster
 167 Dr. Strangepork, the pig
 168 Link Hogthrob, the pig
 169 Zoot, the human
 170 Dr. Bunsen Honeydew, the human
 171 Beaker, the human
 172 Swedish Chef, the human
 173
 174 Animal, the animal
 175 Beaker, the human
 176 Camilla, the chicken
 177 Dr. Bunsen Honeydew, the human
 178 Dr. Strangepork, the pig
 179 Fozzie, the bear
 180 Gonzo, the whatever
 181 Kermit, the frog
 182 Link Hogthrob, the pig
 183 Piggy, the pig
 184 Robin, the frog
 185 Sam, the eagle
 186 Swedish Chef, the human
 187 Sweetums, the monster
 188 Zoot, the human
 189
 190 Kermit, the frog
 191 Gonzo, the whatever
 192 Couldn't find Janice.
 193 @end smallexample