Posts Tagged ‘java’

An Empirical Analysis of QuickSelect and QuickMedian

September 28, 2011

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).

Runtime of QuickMedian and SortMedian Trials, sorted by trial conditions to show regularities