Comparison of Four Algorithms for Selecting the N-Smallest Values (code.activestate.com) 3 points by raymondh 12y ago ↗ HN
[–] raymondh 12y ago ↗ TL;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.
1 comment
[ 3.4 ms ] story [ 15.1 ms ] threadMaintaining 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.