Quick sort median selection

Question

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??

Solution

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

1. divide the list into n/5 subsequences of 5 elements each
2. find the median of each list, by brute force. there will be n/5 of these
3. Let m_1,..., m_n/5 be these medians.
4. recursively find the median of these medians. this will be 1 element, the pivot!

... and some pseudo-code...

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

Comments

[Alcott]

according 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 ?