Qsort
is a C standard library function that implements a sorting algorithm for arrays of arbitrary objects according to a user-provided comparison function. It is named after the "quicker sort" algorithm, which was originally used to implement it in the Unix C library, although the C standard does not require it to implement quicksort. It comes from
The ability to operate on different kinds of data is achieved 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 appears in Version 2 Unix in 1972 as a library assembly language subroutine. Its interface is unlike the modern version, in that it can be pseudo-prototyped asIn Version 3 Unix, the interface is extended by calling compar, with an interface identical to modern-day. This function may be overridden by the user's program to implement any kind of ordering, in an equivalent fashion to the
compar argument to standard .Version 4 Unix adds a C implementation, with an interface equivalent to the standard.
It was rewritten in 1983 for the Berkeley Software Distribution. The function was standardized in ANSI C.
The assembly implementation is removed in Version 6 Unix.
In 1991, Bell Labs employees observed that AT&T 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 adversarial data on-the-fly.Example
The following piece of C code shows how to sort a list of integers usingqsort.- include
int compareInts
// This could be more concisely written as:
int compareInts
// Sort an array of n integers, pointed to by a.
void sortInts
Extensions
Since the comparison function of the originalqsort only accepts two pointers, passing in additional parameters must be done using global variables. The issue was solved by the BSD and GNU Unix-like systems by introducing a 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.In C++, it is faster to use . Compared to, the templated is more type-safe since it does not require access to data items through unsafe pointers, as does. Also, accesses the comparison function using a function pointer, necessitating large numbers of repeated function calls, whereas in, comparison functions may be inlined into the custom object code generated for a template instantiation. In practice, C++ code using is often considerably faster at sorting simple data like integers than equivalent C code using.