Tuesday 29 May 2012

Median of medians algorithm

  1. If n is small, for example n<6, just sort and return the k'th smallest number.( Bound time- 7)
  2. If n>5, then partition the numbers into groups of 5.(Bound time n/5). Sort the numbers within each group. Select the middle elements (the medians). (Bound time- 7n/5)
  3. Call your "Selection" routine recursively to find the median of n/5 medians and call it m. (Bound time-Tn/5)
  4. Compare all n-1 elements with the median of medians m and determine the sets L and R, where L contains all elements <m, and R contains all elements >m. Clearly, the rank of m is r=|L|+1 (|L| is the size or cardinality of L). (Bound time- n)
  5. If k=r, then return m
  6. If k<r, then return k th smallest of the set L .(Bound time T 7n/10)
  7. If k>r, then return k-r th smallest of the set R.
Source: ranger.uta.edu/~gdas/Courses/Fall2004/.../W6Presentation.ppt


This algorithm (O(n)) is used to improve the worst case performance of basic (partitioning) order selection algo used in quicksort (O(n^2)) .
 

11 comments: