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