![]() |
A Variant of Quicksort |
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.