qsort

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 as qsort(void * start, void * end, unsigned length) – sorting contiguously-stored length-long byte strings from the range [start, end).{{cite web |title=UNIX Programmer's Manual, Second Edition |via=The Unix Heritage Society |url=https://www.tuhs.org/Archive/Distributions/Research/Dennis_v2/v2man.pdf#page=193 |page=193 |editor1-link=Ken Thompson |editor2-link=Dennis Ritchie |publisher=Bell Telephone Laboratories |date=June 12, 1972 |access-date=July 24, 2024 |archive-date=July 30, 2023 |archive-url=https://web.archive.org/web/20230730004315/https://www.tuhs.org/Archive/Distributions/Research/Dennis_v2/v2man.pdf#page=193 |url-status=live }} 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).{{cite web |title=UNIX Programmer's Manual, Third Edition |via=The Unix Heritage Society |url=https://minnie.tuhs.org/cgi-bin/utree.pl?file=V3/man/man3/qsort.3 |page=qsort(III) |editor1-link=Ken Thompson |editor2-link=Dennis Ritchie |publisher=Bell Telephone Laboratories |date=February 1973 |access-date=2024-07-24 |archive-date=2023-07-24 |archive-url=https://web.archive.org/web/20230724162149/https://minnie.tuhs.org/cgi-bin/utree.pl?file=V3/man/man3/qsort.3 |url-status=live }}

Version 4 Unix adds a C implementation, with an interface equivalent to the standard.{{cite web |title=UNIX Programmer's Manual, Fourth Edition |via=The Unix Heritage Society |url=https://minnie.tuhs.org/cgi-bin/utree.pl?file=V4/man/man3/qsort.3 |page=qsort(III) |editor1-link=Ken Thompson |editor2-link=Dennis Ritchie |publisher=Bell Telephone Laboratories |date=November 1973 |access-date=2024-07-24 |archive-date=2023-07-24 |archive-url=https://web.archive.org/web/20230724162147/https://minnie.tuhs.org/cgi-bin/utree.pl?file=V4/man/man3/qsort.3 |url-status=live }}

It was rewritten in 1983 for the Berkeley Software Distribution. The function was standardized in ANSI C (1989).

The assembly implementation is removed in Version 6 Unix.{{cite web |title=qsort(III), from UNIX Programmer's Manual, Sixth Edition |website=Unix Archive |url=http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/man/man3/qsort.3 |access-date=2014-09-25 |archive-date=2023-02-25 |archive-url=https://web.archive.org/web/20230225015936/https://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/man/man3/qsort.3 |url-status=live }}

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.{{cite journal |last1=McIlroy |first1=M. D. |title=A killer adversary for quicksort |url=https://www.cs.dartmouth.edu/~doug/mdmspe.pdf |journal=Software: Practice and Experience |volume=29 |pages=341–344 |doi=10.1002/(SICI)1097-024X(19990410)29:4<341::AID-SPE237>3.0.CO;2-R |date=10 April 1999 |issue=4 |s2cid=35935409 |access-date=24 July 2024 |archive-date=19 June 2023 |archive-url=https://web.archive.org/web/20230619014319/https://www.cs.dartmouth.edu/~doug/mdmspe.pdf |url-status=live }}

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

1. include

/* 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);

}

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 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.{{man|3|qsort_r|FreeBSD}}

{{reflist}}

Category:C standard library

Category:Sorting algorithms