{{Short description|Standard library function in the C programming language}} {{other uses|Q sort (disambiguation)}} {{lowercase title}} '''{{mono|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<ref name="v2" /> (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.<ref name="engineering">{{cite journal |first1=Jon L. |last1=Bentley |first2=M. Douglas |last2=McIlroy |title=Engineering a sort function |journal=Software: Practice and Experience |volume=23 |issue=11 |pages=1249–1265 |year=1993 |url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8162 |doi=10.1002/spe.4380231105 |citeseerx=10.1.1.14.8162 |s2cid=8822797 |access-date=2014-01-14 |archive-date=2014-01-16 |archive-url=https://web.archive.org/web/20140116101822/http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8162 |url-status=live }}</ref> It comes from <code><stdlib.h></code> (or <code><cstdlib></code> in C++ Standard Library).
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.<ref>ISO/IEC 9899:201x, Programming Languages—C (draft). §7.22.5. November 16, 2010.</ref>
== 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 as <syntaxhighlight lang="c" inline>void qsort(void* start, void* end, unsigned int length)</syntaxhighlight> – sorting contiguously-stored {{code|length}}-long byte strings from the range [{{mono|start}}, {{mono|end}}).<ref name="v2">{{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 }}</ref> 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 {{mono|memcmp}}. This function may be overridden by the user's program to implement any kind of ordering, in an equivalent fashion to the <code>compar</code> argument to standard {{code|qsort}} (though program-global, of course).<ref>{{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 }}</ref>
Version 4 Unix adds a C implementation, with an interface equivalent to the standard.<ref>{{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 }}</ref> It was rewritten in 1983 for the Berkeley Software Distribution.<ref name="engineering"/> The function was standardized in ANSI C (1989). The assembly implementation is removed in Version 6 Unix.<ref>{{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 }}</ref>
In 1991, Bell Labs employees observed that AT&T and BSD versions of <code>qsort</code> would consume quadratic time for some simple inputs. Thus Jon Bentley and Douglas McIlroy engineered a new faster and more robust implementation.<ref name="engineering"/> McIlroy would later produce a more complex quadratic-time input, termed ''AntiQuicksort'', in 1998. This function constructs adversarial data on-the-fly.<ref>{{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 }}</ref>
== Example == The following piece of C code shows how to sort a list of integers using <code>qsort</code>.
<syntaxhighlight lang="c"> #include <stdlib.h>
// Comparison function. Receives two generic (void) pointers to the items under comparison. int compareInts(const void* p, const void* q) { int x = *(const int*)p; int y = *(const int*)q;
// Avoid returning x - y, which can cause undefined behaviour // because of signed integer overflow. if (x < y) { // Return -1 for ascending, +1 for descending order. return -1; } else if (x > y) { // Return +1 for ascending, -1 for descending order. return 1; } else { return 0; } }
// This could be more concisely written as: int compareInts(const void* p, const void* q) { int x = *(const int*)p; int y = *(const int*)q;
return (x > y) - (x < y); }
// Sort an array of n integers, pointed to by a. void sortInts(int* a, size_t n) { qsort(a, n, sizeof(*a), compareInts); } </syntaxhighlight>
== Extensions == Since the comparison function of the original <code>qsort</code> 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 <code>qsort_r</code> function, which allows for an additional parameter to be passed to the comparison function. The two versions of <code>qsort_r</code> have different argument orders. C11 Annex K defines a <code>qsort_s</code> essentially identical to GNU's <code>qsort_r</code>. The macOS and FreeBSD libcs also contain <code>qsort_b</code>, a variant that uses blocks, an analogue to closures, as an alternate solution to the same problem.<ref>{{man|3|qsort_r|FreeBSD}}</ref>
In C++, it is faster to use {{mono|std::sort}} (or <code>std::ranges::sort</code> from C++20 and onwards). Compared to {{code|::qsort}}, the templated {{code|std::sort}} is more type-safe since it does not require access to data items through unsafe {{code|void}} pointers, as {{code|::qsort}} does. Also, {{code|::qsort}} accesses the comparison function using a function pointer, necessitating large numbers of repeated function calls, whereas in {{code|std::sort}}, comparison functions may be inlined into the custom object code generated for a template instantiation. In practice, C++ code using {{code|std::sort}} is often considerably faster at sorting simple data like integers than equivalent C code using {{code|::qsort}}.<ref>{{cite book | last = Meyers | first = Scott | author-link = Scott Meyers | title = Effective STL: 50 specific ways to improve your use of the standard template library | publisher = Addison-Wesley | date = 2001 | pages = 203 | isbn = 0-201-74962-9}}</ref>
== References == {{reflist}}
Category:C standard library Category:Sorting algorithms