Note that you shouldn't use the algorithm in practice (unless you need certain guarantees) since the average performance isn't that great. This is just like Mergesort vs Quicksort where Mergesort guarantees O(NlogN) yet Quicksort is usually much faster. The constant for the number of comparisons is quite high. Compare this to the <i>average</i> complexity for Quickselect with these pivot strategies:<p>- Random pivot (ie Median of 1) has 3.39N comparisons<p>- Median of 3 has 2.75N<p>If you want the fastest possible algorithm you should follow<p><a href="http://dx.doi.org/10.1109/TSP.2012.2197394" rel="nofollow">http://dx.doi.org/10.1109/TSP.2012.2197394</a><p>which proposes to choose the median of N^{2/3}<i>1/(4</i>pi)^{1/3} elements as the pivot and then also uses a different strategy to choose the second pivot (close to the median yet "safe").<p>Another fast algorithm is Floyd & Rivest's SELECT (yes the same crypto Rivest) which is also asymptotically optimal and implementations exist. (Paper title: "Expected time bounds for selection")
This is one of my favorite algorithms. I use it frequently in my code (example: filtering noise in a real time system) and get giddy when I talk to others about it. One of the contributors to this algorithm was Manuel Blum [0], whose contributions (and his students') touch pretty much every corner of Computer Science.<p>His lecture notes from his course at Carnegie Mellon describe this algorithm quite clearly [1].<p>[0] <a href="http://en.wikipedia.org/wiki/Manuel_Blum" rel="nofollow">http://en.wikipedia.org/wiki/Manuel_Blum</a><p>[1] <a href="http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0125.pdf" rel="nofollow">http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/le...</a>
According to the man himself, this algorithm was found by Manuel Blum when trying to prove that it was impossible to do k selection in linear time deterministically
This is so trivial!<p>Actually, if you use lazy data structures, then sorting the list lazily and taking i-th element will give you the best possible complexity: <a href="http://en.wikipedia.org/wiki/Selection_algorithm#Language_support" rel="nofollow">http://en.wikipedia.org/wiki/Selection_algorithm#Language_su...</a><p>In Haskell, it is nothing more than "ithSmallest xs i = sort xs !! i".
If you like this, go look into the suffix array construction algorithm, called DC3 ("difference cover, modulo 3"). It's even more mindblowing.
The C++ standard library method std::nth_element states complexity; linear time on average. ( <a href="http://en.cppreference.com/w/cpp/algorithm/nth_element" rel="nofollow">http://en.cppreference.com/w/cpp/algorithm/nth_element</a> )<p>I wonder if there are other possible implementations?
I'm coding it in Ruby. Check back tomorrow and I should have it finished. <a href="https://gist.github.com/chadbrewbaker/7202412#file-median-rb" rel="nofollow">https://gist.github.com/chadbrewbaker/7202412#file-median-rb</a>
You can use the same idea in quicksort while choosing the pivot (and make it O(n log n)) but you don't because it is expensive.<p>There is a very nice and simple probabilistic algorithm instead.
So embarrassing when a candidate busted this out on me in an interview - but couldn't quite explain it - so I was convinced he was wrong / out of his mind. Later I looked it up in the CLR and sure enough...
very cool algo!! a C impl: <a href="https://github.com/felipecruz/paa/blob/master/t1/knth_n_mom.c" rel="nofollow">https://github.com/felipecruz/paa/blob/master/t1/knth_n_mom....</a>