The number of bit comparisons used by quicksort: an average-case analysis

DOI10.1214/EJP.V17-1812MaRDI QIDQ428664zbMATH OpenFDO

Authors James Allen Fill, Svante Janson

Publication date 22 June 2012

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.2595

zbMATH Keywords

quicksortaverage-case analysis of algorithmsPoissonization

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Combinatorial probability (60C05)

Abstract: The analyses of many algorithms and data structures (such as digital search trees) for searching and sorting are based on the representation of the keys involved as bit strings and so count the number of bit comparisons. On the other hand, the standard analyses of many other algorithms (such as Quicksort) are performed in terms of the number of key comparisons. We introduce the prospect of a fair comparison between algorithms of the two types by providing an average-case analysis of the number of bit comparisons required by Quicksort. Counting bit comparisons rather than key comparisons introduces an extra logarithmic factor to the asymptotic average total. We also provide a new algorithm, "BitsQuick", that reduces this factor to constant order by eliminating needless bit comparisons.

Recommendations

• The number of bit comparisons used by Quicksort, an average-case analysis
• On a Constant Arising in the Analysis of Bit Comparisons in Quickselect
• Revisiting calculation of moments of number of comparisons used by the randomized quick sort algorithm
• Average case and distributional analysis of dual-pivot quicksort
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• Average-case analysis of quicksort and binary insertion tree height using incompressibility
• Distributional convergence for the number of symbol comparisons used by QuickSort (extended abstract)
• Distributional convergence for the number of symbol comparisons used by QuickSort

Cited in

(12)

• On a Constant Arising in the Analysis of Bit Comparisons in Quickselect
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• scientific article; zbMATH DE number 7359768 (Why is no real title available?)
• Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme
• Analysis of Branch Misses in Quicksort
• Distributional convergence for the number of symbol comparisons used by QuickSort
• On fluctuations of complexity measures for the FIND algorithm
• The number of bit comparisons used by Quicksort, an average-case analysis
• Average-case analysis of quicksort and binary insertion tree height using incompressibility
• Revisiting calculation of moments of number of comparisons used by the randomized quick sort algorithm
• Distributional convergence for the number of symbol comparisons used by QuickSelect
• How Many Comparisons Does Quicksort Use?

This page was built for publication: The number of bit comparisons used by quicksort: an average-case analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428664)