CODEWITHSUNDEEP
algorithmquicksort
venkysmarty
venkysmarty

Reputation: 11431

quick sort improvement using median of three robert sedwick

Following text from quick sort section in algorithms book by Robert Sedwick.

By choosing the three elements from the left, middle, and right of the array, we can incorporate sentinels into this scheme. Sort three elements, then exchange one in the middle with a[r-1], and then run the partitioning algorithm on a[l+1],...,a[r-2]. This improvement is called the median of three method.

The median of three method helps quick sort in three ways.

  1. It makes the worst case much more unlikely to occur in any actual sort. For the sort to take O(N^2) time, two out of the three elements examined must be among the largest or among the smallest elements in the file, and this event must happen consistently thorough most of the partitions.

  2. It eliminates the need for a sentinel key for partitioning, because this function is served by one of the three elements that are examined before partitioning.

  3. It reduce the total average running time of algorithm by about 5 percent.

    template <class Item> 
void exch(Item &A, Item &B) 
      { Item t = A; A = B; B = t; } 

template <class Item> 
void compexch(Item &A, Item &B) 
      { if (B < A) exch(A, B); }

static const int M = 10;
template <class Item>
void quicksort(Item a[], int l, int r)
  {
    if (r-l <= M) return;
    exch(a[(l+r)/2], a[r-1]);  // line 1
    compexch(a[l], a[r-1]);   // line 2.
    compexch(a[l], a[r]);     // line 3.
    compexch(a[r-1], a[r]);   // line 4.
    int i = partition(a, l+1, r-1);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
  }

template <class Item>
void hybridsort(Item a[], int l, int r)
  { quicksort(a, l, r); insertion(a, l, r); }

My questions on above text, Can any one explain with simple example

  1. What does author mean by "worst case much more unlikely to occur in any actual sort. For the sort to take N square time, two out of the three elements examined must be among the largest" ?

  2. What does author mean by "It eliminates the need for a sentinel key for partitioning" ?

  3. In above program what we are achieving in line 1, 2, 3, and 4 which is commented in above code?

Thanks for your time and help!

Upvotes: 2

Views: 6325

Answers (1)

nickponline
nickponline

Reputation: 25914

The strength of the quicksort algorithm is that is divides the data in half and then sorts each half and merges the results. This behaviour is what gives it an O(N log N) complexity. However this is based on the fact when when you divide that data in half you actually divide it in half. However this is not always true. You aren't just dividing the array, you are partitioning into two pieces but comparing each element to the partition element (say P). If an element is less than or equal to P then it goes in the left sub-array otherwise is goes in the right sub-array. So the size of the sub-arrays is heavily dependent on the partition element. If P is equal to the largest or smallest value in the array then one of the sub-arrays will be empty and the quicksort will gain nothing from the "divide phase". If this continues each time then the running time of the algorithm becomes O(N^2)

The "median of three" methods prevent the partition element from being the largest or smallest element of the array by making it the middle valued element of three chosen elements.

The fours lines in the code are effectively sorting three elements in place and choosing the middle one as the new partition. If you are going to compare three elements to determine the median you might as well sort them at the same time.

Upvotes: 3

Related Questions