4

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

quamrana
  • 33,740
  • 12
  • 54
  • 68
james
  • 3,934
  • 11
  • 41
  • 60
  • Umm.. basically you just choose 5, 7, or 11 elements of the array being partitioned and use their median as the pivot. It's not really so different from median-of-3. The main difference might be that for array sizes less than 5, 7 or 11 elements, you should probably do an insertion sort. Then again, it will speed up your quicksort, pretty much regardless of how many elements you are using to find your pivot, to do insertion sorts for arrays that are less than about 10-15 elements. – Justin Peel Apr 09 '11 at 18:08

1 Answers1

6

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

I hope this helps.
Hristo

Community
  • 1
  • 1
Hristo
  • 44,041
  • 64
  • 159
  • 226
  • 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 ? – Alcott Oct 11 '11 at 02:59