Quicksort: Difference between revisions

Revision as of 00:14, 18 April 2025

Revision as of 03:07, 18 April 2025

Line 16:

'''Quicksort''' is an efficient, general-purpose [[sorting algorithm]]. Quicksort was developed by British computer scientist [[Tony Hoare]] in 1959<ref>{{cite web |title=Sir Antony Hoare |publisher=Computer History Museum |access-date=22 April 2015 |url=http://www.computerhistory.org/fellowawards/hall/bios/Antony,Hoare/ |url-status=dead |archive-url=https://web.archive.org/web/20150403184558/http://www.computerhistory.org/fellowawards/hall/bios/Antony%2CHoare/ |archive-date=3 April 2015}}</ref> and published in 1961.<ref name=alg64>{{Cite journal |last1 = Hoare |first1 = C. A. R. |author-link1 = Tony Hoare |title = Algorithm 64: Quicksort |doi = 10.1145/366622.366644 |journal = [[Communications of the ACM|Comm. ACM]] |volume = 4 |issue = 7 |pages = 321 |year = 1961 }}</ref> It is still a commonly used algorithm for sorting. Overall, it is slightly faster than [[merge sort]] and [[heapsort]] for randomized data, particularly on larger distributions.<ref name="skiena">{{cite book |first=Steven S. |last=Skiena |year=2008 |author-link=Steven Skiena |title=The Algorithm Design Manual |url=https://books.google.com/books?id=7XUSn0IKQEgC |publisher=Springer |isbn=978-1-84800-069-8 |page=129}}</ref>

Quicksort is a [[divide-and-conquer algorithm]]. It works by selecting a '"pivot'" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called '''partition-exchange sort'''.<ref>C.L. Foster, ''Algorithms, Abstraction and Implementation'', 1992, {{isbn|0122626605}}, p. 98</ref> The sub-arrays are then sorted [[recursion (computer science)|recursively]]. This can be done [[in-place algorithm|in-place]], requiring small additional amounts of [[Main memory|memory]] to perform the sorting.

Quicksort is a [[comparison sort]], meaning that it can sort items of any type for which a "less-than" relation (formally, a [[total order]]) is defined. It is a comparison-based sort since elements ''a'' and ''b'' are only swapped in case their relative order has been obtained in the transitive closure of prior comparison-outcomes. Most implementations of quicksort are not [[Sorting algorithm#Stability|stable]], meaning that the relative order of equal sort items is not preserved.

Line 23:

== History ==

The quicksort algorithm was developed in 1959 by [[Tony Hoare]] while he was a visiting student at [[Moscow State University]]. At that time, Hoare was working on a [[machine translation]] project for the [[National Physical Laboratory, UK|National Physical Laboratory]]. As a part of the translation process, he needed to sort the words in Russian sentences before looking them up in a Russian-English dictionary, which was in alphabetical order on [[magnetic tape data storage|magnetic tape]].<ref>{{Cite journal |last = Shustek |first = L. |title = Interview: An interview with C.A.R. Hoare |doi = 10.1145/1467247.1467261 |journal = [[Communications of the ACM|Comm. ACM]] |volume = 52 |issue = 3 |pages = 38–41 |year = 2009 |s2cid = 1868477 }}</ref> After recognizing that his first idea, [[insertion sort]], would be slow, he came up with a new idea. He wrote the partition part in Mercury [[Autocode]] but had trouble dealing with the list of unsorted segments. On return to England, he was asked to write code for [[Shellsort]]. Hoare mentioned to his boss that he knew of a faster algorithm and his boss bet a [[Sixpence (British coin)|sixpence]] that he did not. His boss ultimately accepted that he had lost the bet. Hoare published a paper about his algorithm in [[The Computer Journal]] [https://academic.oup.com/comjnl/article/5/1/10/395338?login=false Volume 5, Issue 1, 1962, Pages 10–16]. Later, Hoare learned about [[ALGOL]] and its ability to do recursion, thatwhich enabled him to publish an improved version of the algorithm in ALGOL in ''[[Communications of the ACM|Communications of the Association for Computing Machinery]]'', the premier computer science journal of the time.<ref name=alg64 /><ref>{{Cite web |url = http://anothercasualcoder.blogspot.com/2015/03/my-quickshort-interview-with-sir-tony.html |title = My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort |date = 2015-03-15 |publisher = Marcelo M De Barros }}</ref> The ALGOL code is published in [https://dl.acm.org/doi/pdf/10.1145/366622.366642 Communications of the ACM (CACM), Volume 4, Issue 7 July 1961, pp 321 Algorithm 63: partition and Algorithm 64: Quicksort].

Quicksort gained widespread adoption, appearing, for example, in [[Unix]] as the default library sort subroutine. Hence, it lent its name to the [[C standard library]] subroutine {{mono|[[qsort]]}}<ref name="engineering" /> and in the reference implementation of [[Java (programming language)|Java]].