Content deleted Content added
m Remove duplicate consequent word "avoid" |
I added the fact that quicksort is a comparison-based sort. This notion was added to the page on comparison sorts. The condition is crucial to underpin time analysis. It ensures that the number of comparisons can be used to derive an upper bound for the number of other operations, such as swaps or assignments. |
||
Line 18:
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.
[[Analysis of algorithms|Mathematical analysis]] of quicksort shows that, [[best, worst and average case|on average]], the algorithm takes <math>O(n \log{n})</math> comparisons to sort ''n'' items. In the [[best, worst and average case|worst case]], it makes <math>O(n^2)</math> comparisons.
| |||