The QuickSelect algorithm is an efficient way to find the N-th largest element in a list. The QuickMedian algorithm uses QuickSelect to efficiently find the middle element(s) of the array.
This blog post sketches how QuickSelect and QuickMedian work in general and in my Java implementation. The bulk of the post discusses the plot of QuickMedian vs. SortMedian’s runtime shown below (click the image for more details).
(more…)
Advertisements
