5

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
  • 37,849
  • 12
  • 53
  • 71
Mushahid Hussain
  • 4,052
  • 11
  • 43
  • 62
  • 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

2 Answers2

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
  • 45,559
  • 65
  • 163
  • 230
  • 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
0
  • 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)

Anurag Verma
  • 121
  • 7