Hacker News new | past | comments | ask | show | jobs | submit login

That's funny. I just looked back at my old email, and I used this very quickselect.c implemention back in April 2008. It worked well and was wicked fast.

The algorithm by Blum, Floyd, Pratt, Rivest, and Tarjan takes 24n comparisons in the worst case. A description here:

http://www.ics.uci.edu/~eppstein/161/960130.html

However, this algorithm has an average case performance of 4n comparisons:

http://www.ics.uci.edu/~eppstein/161/960125.html




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: