The number of comparisons in QuickSort (Q7361882)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry Quick_Sort_Cost
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The number of comparisons in QuickSort |
AFP entry Quick_Sort_Cost |
Statements
15 March 2017
0 references
Manuel Eberl
0 references
The number of comparisons in QuickSort (English)
0 references
We give a formal proof of the well-known results about the number of comparisons performed by two variants of QuickSort: first, the expected number of comparisons of randomised QuickSort (i. e. QuickSort with random pivot choice) is 2 (n+1) H n - 4 n , which is asymptotically equivalent to 2 n ln n ; second, the number of comparisons performed by the classic non-randomised QuickSort has the same distribution in the average case as the randomised one.
0 references
