qsort() -- General Function (libc)

Sort arrays in memory
#include <stdlib.h>
void qsort(data, n, size, comp)
char *data; int n, size; int (*comp)();

qsort() is  a generalized algorithm  for sorting arrays of  data in memory,
using  C. A.  R.  Hoare's ``quicksort''  algorithm.  qsort()  works with  a
sequential array  of memory called data,  which is divided into  n parts of
size bytes  each.  In  practice, data  is usually an  array of  pointers or
structures, and size is the  sizeof the pointer or structure.  Each routine
compares pairs of items  and exchanges them as required.  The user-supplied
routine  to  which  comp points  performs  the  comparison.   It is  called
repeatedly, as follows:

    (*comp)(p1, p2)
    char *p1, *p2;

Here, p1 and p2 each point  to a block of size bytes in the data array.  In
practice, they are usually  pointers to pointers or pointers to structures.
The comparison  routine must return  a negative, zero,  or positive result,
depending on whether  p1 is logically less than, equal  to, or greater than
p2, respectively.

Example

For an example of this function, see the entry for malloc().

See Also

libc,
shellsort(),
strcmp(),
stdlib.h,
strncmp()
The Art of Computer Programming, vol. 3
ANSI Standard, §7.10.5.2
POSIX Standard, §8.1

Notes

The COHERENT library  also includes the sorting function shellsort(). These
functions use  different algorithms for  sorting items; each  algorithm has
its  strengths and  weaknesses.   In general,  the  quicksort algorithm  is
faster than the shellsort algorithm for large arrays, whereas the shellsort
algorithm  is  faster for  small  arrays  (say, 50  items  or fewer).   The
quicksort algorithm  also performs poorly on arrays with  a small number of
keys, e.g., an array of 1,000 items whose keys are all `7' and `8'.

To get around these limitations, the COHERENT implementation of qsort() has
an  adaptive algorithm  that  recognizes when  the  quicksort algorithm  is
performing badly, and calls shellsort() in its place.

© 2012 by Stephen A. Ness