Searching and Sorting
*********************

This chapter describes functions for searching and sorting arrays of arbitrary objects.  You pass the appropriate comparison function to be applied as an argument, along with the size of the objects in the array and the total number of elements.

Defining the Comparison Function
================================

In order to use the sorted array library functions, you have to describe how to compare the elements of the array.

To do this, you supply a comparison function to compare two elements of the array.  The library will call this function, passing as arguments pointers to two array elements to be compared.  Your comparison function should return a value the way strcmp (see String/Array Comparison) does: negative if the first argument is ``less'' than the second, zero if they are ``equal'', and positive if the first argument is ``greater''.

Here is an example of a comparison function which works with an array of numbers of type double:

     int
     compare_doubles (const double *a, const double *b)
     {
       double temp = *a - *b;
       if (temp > 0)
         return 1;
       else if (temp < 0)
         return -1;
       else
         return 0;
     }

The header file stdlib.h defines a name for the data type of comparison functions.  This is a GNU extension and thus defined only if you request the GNU extensions.

     int comparison_fn_t (const void *, const void *);

Array Search Function
=====================

To search a sorted array for an element matching the key, use the bsearch function.  The prototype for this function is in the header file stdlib.h.

 -- Function: void * bsearch (const void *KEY, const void *ARRAY, size_t COUNT, size_t SIZE, comparison_fn_t COMPARE)
     The bsearch function searches the sorted array ARRAY for an object that is equivalent to KEY.  The array contains COUNT elements, each of which is of size SIZE.

     The COMPARE function is used to perform the comparison.  This function is called with two pointer arguments and should return an integer less than, equal to, or greater than zero corresponding to whether its first argument is considered less than, equal to, or greater than its second argument.  The elements of the ARRAY must already be sorted in ascending order according to this comparison function.

     The return value is a pointer to the matching array element, or a null pointer if no match is found.  If the array contains more than one element that matches, the one that is returned is unspecified.

     This function derives its name from the fact that it is implemented using the binary search.

Array Sort Function
===================

To sort an array using an arbitrary comparison function, use the qsort function.  The prototype for this function is in stdlib.h.

 -- Function: void qsort (void *ARRAY, size_t COUNT, size_t SIZE, comparison_fn_t COMPARE)
     The QSORT function sorts the array ARRAY.  The array contains COUNT elements, each of which is of size SIZE.

     The COMPARE function is used to perform the comparison on the array elements.  This function is called with two pointer arguments and should return an integer less than, equal to, or greater than zero corresponding to whether its first argument is considered less than, equal to, or greater than its second argument.

     Warning: If two objects compare as equal, their order after sorting is unpredictable.  That is to say, the sorting is not stable. This can make a difference when the comparison considers only part of the elements.  Two elements with the same sort key may differ in other respects.

     If you want the effect of a stable sort, you can get this result by writing the comparison function so that, lacking other reason distinguish between two elements, it compares them by their addresses.

     Here is a simple example of sorting an array of doubles in numerical order, using the comparison function defined above (see Comparison Functions):

          {
            double *array;
            int size;
            ...
            qsort (array, size, sizeof (double), compare_doubles);
          }

     The qsort function derives its name from the fact that it was originally implemented using the algorithm ``quick sort''.

Searching and Sorting Example
=============================

Here is an example showing the use of qsort and bsearch with an array of structures.  The objects in the array are sorted by comparing their name fields with the strcmp function. Then, we can look up individual objects based on their names.

          [file search.c.texi not included]

The output from this program looks like:

     Animal, the animal
     Beaker, the human
     Camilla, the chicken
     Dr. Bunsen Honeydew, the human
     Dr. Strangepork, the pig
     Fozzie, the bear
     Gonzo, the whatever
     Kermit, the frog
     Link Hogthrob, the pig
     Piggy, the pig
     Robin, the frog
     Sam, the eagle
     Swedish Chef, the human
     Sweetums, the monster
     Zoot, the human

     Kermit, the frog
     Gonzo, the whatever
     Couldn't find Janice.