QuickHeapsort: modifications and improved analysis. QuickHeapsort is a combination of Quicksort and Heapsort. We show that the expected number of comparisons for QuickHeapsort is always better than for Quicksort if a usual median-of-constant strategy is used for choosing pivot elements. In order to obtain the result we present a new analysis for QuickHeapsort splitting it into the analysis of the partition-phases and the analysis of the heap-phases. This enables us to consider samples of non-constant size for the pivot selection and leads to better theoretical bounds for the algorithm. Furthermore, we introduce some modifications of QuickHeapsort. We show that for every input the expected number of comparisons is at most nlog 2 n-0·03n+o(n) for the in-place variant. If we allow n extra bits, then we can lower the bound to nlog 2 n-0·997n+o(n). Thus, spending n extra bits we can save more that 0.96n comparisons if n is large enough. Both estimates improve the previously known results. Moreover, our non-in-place variant does essentially use the same number of comparisons as index based Heapsort variants and Relaxed-Weak-Heapsort which use nlog 2 n-0·9n+o(n) comparisons in the worst case. However, index based Heapsort variants and Relaxed-Weak-Heapsort require Θ(nlogn) extra bits whereas we need n bits only. Our theoretical results are upper bounds and valid for every input. Our computer experiments show that the gap between our bounds and the actual values on random inputs is small. Moreover, the computer experiments establish QuickHeapsort as competitive with Quicksort in terms of running time.
Keywords for this software
References in zbMATH (referenced in 11 articles , 2 standard articles )
Showing results 1 to 11 of 11.
- Edelkamp, Stefan; Weiß, Armin; Wild, Sebastian: QuickXsort: a fast sorting scheme in theory and practice (2020)
- Bahig, Hazem M.: Complexity analysis and performance of double hashing sort algorithm (2019)
- Edelkamp, Stefan; Weiß, Armin: Worst-case efficient sorting with QuickMergesort (2019)
- Wild, Sebastian: Average cost of QuickXsort with pivot sampling (2018)
- Diekert, Volker; Weiß, Armin: QuickHeapsort: modifications and improved analysis (2016)
- Cantone, Domenico; Hofri, Micha: Further analysis of the remedian algorithm (2013)
- Diekert, Volker; Weiß, Armin: QuickHeapsort: modifications and improved analysis (2013)
- Kocamaz, Uğur Erkin: Increasing the efficiency of quicksort using a neural network based algorithm selection model (2013) ioport
- Wang, Xiao-Dong; Wu, Ying-Jie: An improved HEAPSORT algorithm with (n \logn - 0.788928 n) comparisons in the worst case (2007) ioport
- Cantone, D.; Cincotti, G.: QuickHeapsort, an efficient mix of classical sorting algorithms (2002)
- Cantone, Domenico; Cincotti, Gianluca: QuickHeapsort, an efficient mix of classical sorting algorithms (2000)