A Variant of Quicksort

Title:

A Variant of Quicksort

Language:

C

Author:

Philip J. Erdelsky

• pje@efgh.com
• http://www.alumni.caltech.edu/~pje/

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.