Quick sort median selection

As we can choose median of 3 element partitioning to implement quick so开发者_Go百科rt. Likewise can we choose median of 5, 7, or 11 element to implement quick sort? If so, then how??

---

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

---

• The median-of-medians algorithm is a deterministic linear-time selection algorithm.
• Using this algorithm, we can improve quick sort algorithm!
• The average case time complexity is O(nlogn) and
• The worst case time complexity is O(n2) n square.

However we can improve it using median of medians.

kthSmallest(arr[0..n-1], k)

1. Divide arr[] into ⌈n/5⌉ groups where size of each group is 5
   except possibly the last group which may have less than 5 elements.

2. Sort the above created ⌈n/5⌉ groups and find median of all groups. Create an auxiliary array 'median[]' and store medians
   of all ⌈n/5⌉ groups in this median array.

3. // Recursively call this method to find median of median[0..⌈n/5⌉-1] medOfMed = kthSmallest(median[0..⌈n/5⌉-1], ⌈n/10⌉)

4. Partition arr[] around medOfMed and obtain its position. pos = partition(arr, n, medOfMed)

5. If pos == k return medOfMed

6. If pos > k return kthSmallest(arr[l..pos-1], k)

7. If pos < k return kthSmallest(arr[pos+1..r], k-pos+l-1)

Now time complexity is : O(n)