# Qsort

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Qsort
> Markdown URL: https://mediated.wiki/source/Qsort.md
> Source: https://en.wikipedia.org/wiki/Qsort
> Source revision: 1314080164
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Standard library function in the C programming language}}
{{other uses|Q sort (disambiguation)}}
{{lowercase title}}
'''{{mono|qsort}}''' is a [C standard library](/source/C_standard_library) [function](/source/Function_(computer_programming)) that implements a [sorting algorithm](/source/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](/source/quicksort) variant due to R. S. Scowen), which was originally used to implement it in the [Unix](/source/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](/source/C%2B%2B_Standard_Library)).

The ability to operate on different kinds of data (''[polymorphism](/source/Polymorphism_(computer_science))'') is achieved by taking a [function pointer](/source/function_pointer) to a [three-way comparison](/source/three-way_comparison) function, as well as a parameter that specifies the size of its individual input objects. The [C standard](/source/ISO_C) requires the comparison function to implement a [total order](/source/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](/source/Version_2_Unix) in 1972 as a library [assembly language](/source/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](/source/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](/source/Bell_Labs) |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](/source/little-endian) integers, or any other data structures.

In [Version 3 Unix](/source/Version_3_Unix), the interface is extended by calling compar(III), with an interface identical to modern-day {{mono|[memcmp](/source/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](/source/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](/source/Bell_Labs) |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](/source/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](/source/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](/source/Bell_Labs) |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](/source/Berkeley_Software_Distribution).<ref name="engineering"/> The function was standardized in [ANSI C](/source/ANSI_C) (1989).
The assembly implementation is removed in [Version 6 Unix](/source/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](/source/time_complexity) for some simple inputs. Thus [Jon Bentley](/source/Jon_Bentley_(computer_scientist)) and [Douglas McIlroy](/source/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](/source/global_variables). The issue was solved by the [BSD](/source/Berkeley_Software_Distribution) and [GNU](/source/GNU) [Unix-like](/source/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](/source/C11_(C_standard_revision)) defines a <code>qsort_s</code> essentially identical to GNU's <code>qsort_r</code>. The [macOS](/source/macOS) and [FreeBSD](/source/FreeBSD) libcs also contain <code>qsort_b</code>, a variant that uses [blocks](/source/Blocks_(C_language_extension)), an analogue to [closures](/source/Closure_(computer_science)), 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](/source/Sort_(C%2B%2B))}} (or <code>std::ranges::sort</code> from [C++20](/source/C%2B%2B20) 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](/source/inline_expansion) 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

---
Adapted from the Wikipedia article [Qsort](https://en.wikipedia.org/wiki/Qsort) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Qsort?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.