LOGO

A Variant of Quicksort

Title:
A Variant of Quicksort
Language:
C
Author:
Philip J. Erdelsky
Date:
February 6, 2001
Usage:
Public domain; no restrictions on use
Portability:
Any C compiler
Keywords:
Quicksort, Sorting
Abstract:
A variant of the qsort() library function which passes a user-defined pointer to the comparison function.
Source:
qsort.txt

The qsort() function, which sorts an array of arbitrary items, is available with most C compilers. This is a variant of the qsort() function with one important additional feature: a user-defined parameter is passed to the comparison function.

     QuickSort(base, count, size, compare, pointer);

     void *base;      base of array to be sorted

     int count;       number of elements in array

     int size;        number of bytes in each element

     int (*compare);  comparison function

     void *pointer;   user-defined pointer to be passed to compare()

The comparison function is called as follows:

     n = (*compare)(p, q, pointer);

     const void *p;   pointer to element

     const void *q;   pointer to another element

     void *pointer;   copy of pointer submitted to QuickSort()

     int n;           negative if *p precedes *q in sorted order;
                      positive if *p follows *q, and zero if the
                      order of *p and *q is irrelevant

For example, the following comparison function and call will sort an array of fixed-length strings:

     int compare(const void *p, const void *q, void *length)
     {
       int i, n;
       for (i = 0; i < (int) length; i++)
       {
         n = ((unsigned char *) p)[i] - ((unsigned char *) q)[i];
         if (n != 0)
           break;
       }
       return n;
     }

     QuickSort(base, count, size, compare, (void *) size);

Notice that with the standard function qsort(), the size would have to be passed through a global variable, which renders the function non-reentrant.