Content deleted Content added
Giftpflanze (talk | contribs) m →Hoare partition scheme: harmonize p-1 formatting |
testing edit feature Tags: Reverted Visual edit |
||
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 a very 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.
| |||