A Detailed Analysis of Quicksort Algorithms with Experimental Mathematics
By Yukun Yao
.pdf
LaTeX source
Written: April-May 2019
We study several variants of single-pivot and multi-pivot Quicksort
algorithms and consider them as discrete probability problems. With
experimental mathematics, explicit expressions for expectations, vari-
ances and even higher moments of their numbers of comparisons and
swaps can be obtained. For some variants, Monte Carlo experiments
are performed, the numerical results are demonstrated and the scaled
limiting distribution is also discussed.
Accompanying Maple package is QuickSort.txt and Findrec.txt