The number of bit comparisons used by quicksort: an average-case analysis
From MaRDI portal
Publication:428664
DOI10.1214/EJP.V17-1812zbMATH Open1244.68090arXiv1202.2595MaRDI QIDQ428664FDOQ428664
Svante Janson, James Allen Fill
Publication date: 22 June 2012
Published in: Electronic Journal of Probability (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1202.2595
Recommendations
- The number of bit comparisons used by Quicksort, an average-case analysis
- Analysis of the expected number of bit comparisons required by quickselect
- Analysis of the expected number of bit comparisons required by quickselect
- 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 (10)
- On a Constant Arising in the Analysis of Bit Comparisons in Quickselect
- The Number of Symbol Comparisons in QuickSort and QuickSelect
- Title not available (Why is that?)
- Analysis of Branch Misses in Quicksort
- Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme
- Distributional convergence for the number of symbol comparisons used by QuickSort
- 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)
