QuickSort and MergeSort

Idea of the QuickSort

• subdivide the list by arbitrarily picking a middle number (pivot)
• put all values less than pivot before and all values greater behind
• implement with two pointers from opposite end
• pivot is in correct position and splits the list into two lists
• sort first sublist and second sublist recursively

Work through an example

12  4  34  17  6  3  9  21  15  10  5  11  25  8  18

An animation site maintained by Jason Harrison at harrison@cs.ubc.ca.

Quicksort Code

public static void quickSort(  int first , int last ) 
{
   if (first < last)
   {
     int splitPoint;
     splitPoint = split(first , last);
     // values[first] .. values[splitPoint-1] <= splitVal
     // values[splitPoint+1] .. values[last] > splitVal

     quickSort(first , splitPoint-1);
     quickSort(splitPoint+1 , last);
}

static int split( int first, int last )
{
   int splitVal = values[first];   
   int saveF = first;
   boolean onCorrectSide;

   first++;
   do
   {
     onCorrectSide = true;
     while (onCorrectSide)
       if (values[first] > splitVal)
         onCorrectSide = false;
       else
       {
         first++;
         onCorrectSide = (first <= last);
       }

      onCorrectSide = (first <= last);
      while (onCorrectSide)
        if (values[last] <= splitVal)
          onCorrectSide = false;
        else
        {
          last--;
          onCorrectSide = (first <= last);
        }

      if (first < last)
      {
        swap(first, last);
        first++;
        last--;
      }
    } while (first <= last);

    swap(saveF, last);
    return last;

}   

Analysis of QuickSort

Count of comparisons of array elements in the algorithm as a measure of the complexity: Let C(n) be the number of comparisons for the quicksort of list of size n. Again we use recurrence relations and we want to solve for C(n) 

Base: C(1) = C(0) = 0

In general: C(n) = n-1 + C(t) + C(n-t-1)

that is, C(n) = number of comparisons in the non-recursive part (partitioning)

+ number of comparisons in the recursive call for the top partition (t is the size of the top)
+ number of comparisons in the recursive call for the bottom partition

For the average or worst case analysis we want to know t

Worst case: t==0

C(1) = 0
C(2) = 1 + C(1) =1
C(3) = 2 + C(2) = 2+1
C(4) = 3 + C(3) =3+2+1
....
C(n) = n-1 + C(n-1) = (n-1) + (n-2) + ...+3+2+1
     = n(n-1)/2
     =O(n²)

(similar for number of swaps: worst case O(n²) 

So the quicksort can degrade to a selection sort performance, but the data almost has to be arranged to cause the pivot to always be an extreme value.

Average case comparisons

• Assume each permutation is equally likely
• p represents the position of finally placed pivot

So C(n,p) = the number of comparisons for n elements with pivot at position p

and C(n,p) = n-1 + C(p-1) + C(n-p)

where t = p-1

To compute C(n) we must average C(n,p) for p=1,2,..,n

C(n) = ¹/_nΣ C(n,p), for p=1,2...,n

C(n) = ¹/_n Σ(n-1 + C(p-1) + C(n-p))

C(n) = (n-1) + ¹/_n( [C(0) + C(n-1)]

+ [C(1) + C(n-2)]

+ [C(2) + C(n-3)]
+...
+ [C(n-1) + C(0)] )

C(n) = (n-1) + ²/_n (C(0) + C(1) + ... + C(n-1))

A: nC(n) = n²-n + 2C(0) + 2C(1) + ...+ 2C(n-1)

Note C(n-1) = (n-2) + 2/(n-1) (C(0) + ... + C(n-2))

B: (n-1)C(n-1) = n²-n-2(n-1) + 2C(0) + ...+ 2C(n-2)

Subtracting B from A

nC(n) - (n-1)C(n-1) = 2(n-1) + 2C(n-1)

nC(n) = 2(n-1) + (n-1)C(n-1) + 2C(n-1)

nC(n) = 2(n-1) + (n+1)C(n-1)

C(n)/_(n+1) = 2(n-1)/_n(n+1) + C(n-1)/_n

when you have a pattern like C(n) = f(n) + C(n-1), the recurrence relation is solved by summing the f(n) term

C(n)/_(n+1) = 0 + 1/3 + 1/3 + 1/4+ 1/5 + 5/21 + 4/14 + 7/36 + ...

This sequence is bounded by the harmonic sequence : x(1/2 + 1/3+ 1/4+ 1/5+ ...) which is O(log n)

C(n)/_(n+1) = O(log n)

so

C(n) = O(n log n)