Quick sort median selection
10,891
You should look into the Median of Medians algorithm. It is a linear time algorithm with the following recurrence...
T(n) ≤ T(n/5) + T(7n/10) + O(n)
... which is O(n). The algorithm details...
 divide the list into n/5 subsequences of 5 elements each
 find the median of each list, by brute force. there will be n/5 of these
 Let m_1,..., m_n/5 be these medians.
 recursively find the median of these medians. this will be 1 element, the pivot!
... and some pseudocode...
MedianOfMedians (A[1],...,A[n])
begin
for i=1 to n/5 do {
let m_i be the median of A[5i − 4], A[5i − 3],..., A[5i];
}
pivot = Select(m1,...,m_n/5, n/10); // the pivot
return pivot
end
References
 http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm__Median_of_Medians_algorithm
 Median of Medians in Java
 http://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf
 http://www.soe.ucsc.edu/classes/cmps102/Spring05/selectAnalysis.pdf
 http://webee.technion.ac.il/courses/044268/w0809_website/recitations/Median.pdf
I hope this helps.
Hristo
Author by
james
Updated on June 04, 2022Comments

james 7 months
As we can choose median of 3 element partitioning to implement quick sort. Likewise can we choose median of 5, 7, or 11 element to implement quick sort? If so, then how??

Alcott over 11 yearsaccording to your code, we can just find the pivot closest to the median of the whole array, then partition the whole array into 2 parts? If the lower part has fewer numbers than the higher part, then do what ?