2 ms·
Comparison of Four Algorithms for Selecting the N-Smallest Values
- raymondh 13y agoTL;DR -- Maintaining a small heap wins. Quicksort-style selection loses. Summary results appear at the end of the article. Maintaining a small heap takes 105,714 to 106,452 comparisons. Building a big heap takes 166,525 to 166,629 comparisons. Quick select followed by a second pass takes 222,351 to 496,865 comparisons (widely variable results depending on lucky or unlucky pivots). Quick select with intermediate small concatenated sorts takes 131,171 to 217,504 comparisons.