Abstract: |
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) Hn -
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. |
BibTeX: |
@article{Quick_Sort_Cost-AFP,
author = {Manuel Eberl},
title = {The number of comparisons in QuickSort},
journal = {Archive of Formal Proofs},
month = mar,
year = 2017,
note = {\url{http://isa-afp.org/entries/Quick_Sort_Cost.html},
Formal proof development},
ISSN = {2150-914x},
}
|