Qsort

qsort is a C standard library function that implements a polymorphic sorting algorithm for arrays of arbitrary objects according to a user-provided comparison function. It is named after the "quicker sort" algorithm (a quicksort variant due to R. S. Scowen), which was originally used to implement it in the Unix C library, although the C standard does not require it to implement quicksort.

Implementations of the qsort function achieve polymorphism, the ability to sort different kinds of data, by taking a function pointer to a three-way comparison function, as well as a parameter that specifies the size of its individual input objects. The C standard requires the comparison function to implement a total order on the items in the input array.

History

A qsort function was implemented by Lee McMahon in 1972. It was in place in Version 3 Unix as a library function, but was then an assembler subroutine.

A C version, with roughly the interface of the standard C version, was in-place in Version 6 Unix. It was rewritten in 1983 for BSD. The function was standardized in ANSI C (1989).

In 1991, Bell Labs employees observed that McMahon's and BSD versions of qsort would consume quadratic time for some simple inputs. Thus Jon Bentley and Douglas McIlroy engineered a new faster and more robust implementation. McIlroy would later produce a more complex quadratic-time input, termed ''AntiQuicksort'', in 1998. This function constructs adversary data on-the-fly.

Example

The following piece of C code shows how to sort a list of integers using qsort.

#include

/* Comparison function. Receives two generic (void) pointers to the items under comparison. */
int compare_ints(const void *p, const void *q)

/* Sort an array of n integers, pointed to by a. */
void sort_ints(int *a, size_t n)

Extensions

Since the comparison function of the original qsort only accepts two pointers, passing in additional parameters (e.g. producing a comparison function that compares by the two value's difference with another value) must be done using global variables. The issue was solved by the BSD and GNU Unix-like systems by a introducing qsort_r function, which allows for an additional parameter to be passed to the comparison function. The two versions of qsort_r have different argument orders. C11 Annex K defines a qsort_s essentially identical to GNU's qsort_r. The macOS and FreeBSD libcs also contain qsort_b, a variant that uses blocks, an analogue to closures, as an alternate solution to the same problem.

References

{{reflist

C standard library
Sorting algorithms