Data Structure: Quick Sort

 

Good points

• It is in-place since it uses only a small auxiliary stack.
• It requires only n log(n) time to sort n items.
• It has an extremely short inner loop
• This algorithm has been subjected to a thorough mathematical analysis, a very precise statement can be made about performance issues.

Bad Points

• It is recursive. Especially if recursion is not available, the implementation is extremely complicated.
• It requires quadratic (i.e., n²) time in the worst-case.
• It is fragile i.e., a simple mistake in the implementation can go unnoticed and cause it to perform badly.

QuickSort

1. If p < r then
2.     q Partition (A, p, r)
3.     Recursive call to Quick Sort (A, p, q)
4.     Recursive call to Quick Sort (A, q + r, r)

 

Partitioning the Array

PARTITION (A, p, r)

1. x ← A[p]
2. i ← p-1
3. j ← r+1
4. while TRUE do
5.     Repeat j ← j-1
6.     until A[j] ≤ x
7.     Repeat i ← i+1
8.     until A[i] ≥ x
9.     if i < j
10.         then exchange A[i] ↔ A[j]
11.         else return j

 

Array of Same Elements

 

Performance of Quick Sort

Best Case

T(n) = T(n/2) + T(n/2) + (n)
       = 2T(n/2) + (n)

 

Worst case Partitioning

  

Randomized Quick Sort

RANDOMIZED_PARTITION (A, p, r)

i ← RANDOM (p, r)
Exchange A[p] ↔ A[i]
return PARTITION (A, p, r)

RANDOMIZED_QUICKSORT (A, p, r)

If p < r then
    q ← RANDOMIZED_PARTITION (A, p, r)
    RANDOMIZED_QUICKSORT (A, p,q)
    RANDOMIZED_QUICKSORT (A, q+1,     

r)

 

Analysis of Quick sort

Let T(n) be the worst-case time for QUICK SORT on input size n. We have a recurrence

T(n) = max_1≤q≤n-1 (T(q) + T(n-q)) + (n)             --------- 1

where q runs from 1 to n-1, since the partition produces two regions, each having size at least 1.
Now we guess that T(n) ≤ cn² for some constant c.
Substituting our guess in equation 1.We get

    T(n) = max_1≤q≤n-1 (cq² ) + c(n - q²)) + (n)
           = c max (q² + (n - q)²) +  (n)

Since the second derivative of expression q² + (n-q)²  with respect to q is positive. Therefore, expression achieves a maximum over the range 1≤ q  ≤ n -1 at one of the endpoints. This gives the bound max (q² + (n- q)²)) 1 + (n -1)^{2 =} n² + 2(n -1).
Continuing with our bounding of T(n) we get

    T(n) ≤ c [n² - 2(n-1)] + (n)
            = cn² - 2c(n-1) + (n)

Since we can pick the constant so that the 2c(n -1) term dominates the (n) term we have

     T(n)  ≤  cn²

Thus the worst-case running time of quick sort is (n²).

 

Average-case Analysis

If the split induced by RANDOMIZED_PARTITION puts constant fraction of elements on one side of the partition, then the recurrence tree has depth (lgn) and (n) work is performed at (lg n) of these level. This is an intuitive argument why the average-case running time of  RANDOMIZED_QUICKSORT is (n lg n).
Let T(n) denotes the average time required to sort an array of n elements. A call to RANDOMIZED_QUICKSORT with a 1 element array takes a constant time, so we have T(1) =  (1).
After the split RANDOMIZED_QUICKSORT calls itself to sort two subarrays. The average time to sort an arrayA[1 . . q] is T[q] and the average time to sort an array A[q+1 . . n] is T[n-q]. We have

        T(n) = 1/n (T(1) + T(n-1) + ^n-1∑_q=1 T(q) + T(n-q))) + (n)    ----- 1

We know from worst-case analysis

T(1) =  (1) and T(n -1) = O(n²)
T(n) = 1/n ((1) + O(n²)) + 1/n ^n-1∑_q=1 (r(q) + T(n - q)) ₊ (n)
       = 1/n  ^n-1∑_q=1(T(q) + T(n - q)) + (n)                          ------- 2
       = 1/n[2  ^n-1∑_k=1(T(k)] + (n)
       = 2/n ^n-1∑_k=1(T(k) + (n)                                           --------- 3

Solve the above recurrence using substitution method. Assume inductively that T(n) ≤ anlgn + b for some constants a > 0 and b > 0.
If we can pick 'a' and 'b' large enough so that n lg n + b > T(1). Then for n > 1, we have

T(n) ≥ ^n-1∑_k=1 2/n (aklgk + b) + (n)
        = 2a/n ^n-1∑_k=1 klgk - 1/8(n²) +  2b/n (n -1) + (n)     ------- 4

At this point we are claiming that

^n-1∑_k=1 klgk  ≤  1/2 n² lgn - 1/8(n²)

Stick this claim in the equation 4 above and we get

T(n)  ≤   2a/n [1/2 n²  lgn - 1/8(n²)] + 2/n b(n -1) + (n)
         ≤  anlgn - an/4 + 2b + (n)                                  ---------- 5

In the above equation, we see that (n) + b and an/4 are polynomials and we certainly can choose 'a' large enough so that an/4 dominates (n)  + b.
We conclude that QUICKSORT's average running time is (n lg(n)).

 Implementation

void quickSort(int numbers[], int array_size)
{
  q_sort(numbers, 0, array_size - 1);
}


void q_sort(int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}