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[1] (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.[2]
The ability to operate on different kinds of data (polymorphism) 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.[3]
History
editA 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 as qsort(void * start, void * end, unsigned length)
– sorting contiguously-stored length-long byte strings from the range [start, end).[1] This, and the lack of a replaceable comparison function, makes it unsuitable to properly sort the system's little-endian integers, or any other data structures.
In Version 3 Unix, the interface is extended by calling compar(III), with an interface identical to modern-day memcmp. 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 qsort (though program-global, of course).[4]
Version 4 Unix adds a C implementation, with an interface equivalent to the standard.[5] It was rewritten in 1983 for the Berkeley Software Distribution.[2] The function was standardized in ANSI C (1989). The assembly implementation is removed in Version 6 Unix.[6]
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.[2] McIlroy would later produce a more complex quadratic-time input, termed AntiQuicksort, in 1998. This function constructs adversary data on-the-fly.[7]
Example
editThe following piece of C code shows how to sort a list of integers using qsort.
#include <stdlib.h>
/* Comparison function. Receives two generic (void) pointers to the items under comparison. */
int compare_ints(const void *p, const void *q) {
int x = *(const int *)p;
int y = *(const int *)q;
/* Avoid return x - y, which can cause undefined behaviour
because of signed integer overflow. */
if (x < y)
return -1; // Return -1 if you want ascending, 1 if you want descending order.
else if (x > y)
return 1; // Return 1 if you want ascending, -1 if you want descending order.
return 0;
// All the logic is often alternatively written:
return (x > y) - (x < y);
}
/* Sort an array of n integers, pointed to by a. */
void sort_ints(int *a, size_t n) {
qsort(a, n, sizeof(*a), compare_ints);
}
Extensions
editSince 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 an 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.[8]
References
edit- ^ a b "UNIX Programmer's Manual, Second Edition" (PDF). Bell Telephone Laboratories. June 12, 1972. p. 193. Archived (PDF) from the original on July 30, 2023. Retrieved July 24, 2024 – via The Unix Heritage Society.
- ^ a b c Bentley, Jon L.; McIlroy, M. Douglas (1993). "Engineering a sort function". Software: Practice and Experience. 23 (11): 1249–1265. CiteSeerX 10.1.1.14.8162. doi:10.1002/spe.4380231105. S2CID 8822797. Archived from the original on 2014-01-16. Retrieved 2014-01-14.
- ^ ISO/IEC 9899:201x, Programming Languages—C (draft). §7.22.5. November 16, 2010.
- ^ "UNIX Programmer's Manual, Third Edition". Bell Telephone Laboratories. February 1973. p. qsort(III). Archived from the original on 2023-07-24. Retrieved 2024-07-24 – via The Unix Heritage Society.
- ^ "UNIX Programmer's Manual, Fourth Edition". Bell Telephone Laboratories. November 1973. p. qsort(III). Archived from the original on 2023-07-24. Retrieved 2024-07-24 – via The Unix Heritage Society.
- ^ "qsort(III), from UNIX Programmer's Manual, Sixth Edition". Unix Archive. Archived from the original on 2023-02-25. Retrieved 2014-09-25.
- ^ McIlroy, M. D. (10 April 1999). "A killer adversary for quicksort" (PDF). Software: Practice and Experience. 29 (4): 341–344. doi:10.1002/(SICI)1097-024X(19990410)29:4<341::AID-SPE237>3.0.CO;2-R. S2CID 35935409. Archived (PDF) from the original on 19 June 2023. Retrieved 24 July 2024.
- ^ FreeBSD Library Functions Manual –