Hacker News Reader

there is an algorithm called quick-select. getting median of an array should not require full sort of the whole array, only a partial sort is needed to get the median. quick-select does this.

View on HN

I just discovered the name of this. I visualized that you can do a quicksort but only recurse one of the partitions each time--the one that contains the median index. It has the same worst-case O(n^2) and can be fixed the same way choosing the median pivot of 3 potential pivots. Apparently C++'s `std::nth_element` uses quick-select and since if you choose a different target index can find any percentile not just the median.

I assume that "index" in this case is for the index in the fully sorted list? i.e. if you're looking for the 50th place in a 100 item list, then it's 50th place in the sorted list you want.

But as you don't know what value that is, how do you know which partition it's in?

(I am feeling very stupid today and hoping someone can explain this to me)

Never mind, you're keeping the parts that are going to end up in that sorted location. That makes sense.

This visualisation made it click for me: https://www.youtube.com/watch?v=HylYYer2hR4

Reply on news.ycombinator.com