Qsort: Difference between revisions

Revision as of 11:30, 20 July 2016

Latest revision as of 10:59, 8 July 2025

(42 intermediate revisions by 26 users not shown)

Line 1:

{{Short description|Standard library function in the C programming language}}

{{other uses|Q sort (disambiguation)}}

{{lowercase title}}

'''qsort''' is a [[C standard library]] function that implements a [[PolymorphismFunction (computer scienceprogramming)|polymorphicfunction]] 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—PracticeSoftware: 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>

ImplementationsThe ofability theto qsortoperate functionon achievedifferent kinds of data (''[[Polymorphism (computer science)|polymorphism]],'') theis ability to sort different kinds of data,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 [[ISO C|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 was in place in [[Research Unix|Version 3 Unix]] of 1973, but was then an [[assembly language|assembler]] subroutine.<ref>{{cite web |title=qsort(III), from UNIX Programmer's Manual, Third Edition |website=Unix Archive |url=http://minnie.tuhs.org/cgi-bin/utree.pl?file=V3/man/man3/qsort.3}}</ref> A C version, with roughly the interface of the standard C version, was in-place 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}}</ref>

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 <code>qsort(void * start, void * end, unsigned length)</code> – sorting contiguously-stored '''length'''-long byte strings from the range ['''start''', '''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_Labs|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.

It was rewritten in 1983 at [[Berkeley Software Distribution|Berkeley]].<ref name="engineering"/>

The function was standardized in [[ANSI C]] (1989).

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 <code>compar</code> argument to standard '''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_Labs|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>

==Example==

[[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_Labs|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 atfor the [[Berkeley Software Distribution|Berkeley]].<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 qsort would consume [[time complexity|quadratic time]] for some simple inputs. Thus [[Jon Bentley (computer scientist)|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 qsort.

<sourcesyntaxhighlight lang="c">

#include <stdlib.h>

/* Comparison function. Receives two generic (void) pointers to the items under comparison. */

int comparecompare_ints(const void *p, const void *q) {

int x = *(const int *)p;

int y = *(const int *)q;

Line 22 ⟶ 31:

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(int*a), compare()compare_ints);

}

</syntaxhighlight>

</source>

==References 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 [[Berkeley Software Distribution|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 (C standard revision)|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 (C language extension)|blocks]], an analogue to [[Closure (computer science)|closures]], as an alternate solution to the same problem.<ref>{{man|3|qsort_r|FreeBSD}}</ref>

{{reflist}}

== References ==

{{software-eng-stub}}

{{reflist}}

[[Category:C standard library]]