Quick Sort

Developed by Tony Hoare early in 1950s, Quick Sort follows the DnC pattern but without the COMBINE phase in common DnC paradigm.

An animated example: Quick Sort Animation

Fundamental Ideas

Given an input array of length n, choose a pivot in the array and partition around it in order that the left half of array has elements less than the value of the pivot while the right half of array has elements larger than the value of the pivot. It applies to all recursive calls with all sub-arrays until the base case in order that all elements are sorted in place.

Unlike the Merge Sort, Quick Sort is implemented in a style of sort-in-place with little extra memory usage. Quick Sort is prevalent in many practical applications and its average-case running time Ο(n ⋅ log n) equates many of existing performant comparison-based implementations like MergeSort.

Different partition methods incur distinct expected running time in total. It is widely adopted to use randomized partition but the naive partition methods are still worth to study.

Pseudocode

QUICK_SORT(A, low, high)
  if low < high
    p := PARTITION(A, low, high)
    QUICK_SORT(A, low, p - 1)
    QUICK_SORT(A, p + 1, high)

Note: partition methods might vary in accordance with different inputs. Of many schemes, the media-of-three is most recommended choice in practical use.

Partition Schemes

Lomuto Partition

Lomuto Partition scheme chooses the last element from the array as the pivot as the recursion goes on. It is considered an introductory scheme for QuickSort yet less efficient than Hoare Partition scheme.

LOMUTO_PARTITION(A, low, high)
  pivot := A[high]
  i := low - 1
  for j := low to high
    if A[j] ⩽ pivot
      i := i + 1
      if i ≠ j
        swap A[i] with A[j]
  return i

Hoare Partition

In the paper of Quicksort written by Hoare, an original partition method is adopted.

The fundamental idea is to always partition around the first element in the array. Two indices are used in both ends of the sub-arrays and progress towards each other to the middle until an inversion of a pair is found.

HOARE_PARTITION(A, low, high)
  pivot := A[low]
  i := low - 1
  j := high + 1
  loop
    do
      i := i + 1
    while A[i]  pivot

    if i ⩾ j
      return j

    swap A[i] with A[j]

A modest comparison of Hoare's and Lomuto's partition scheme shows that Hoare partition runs three times smaller of swaps on average than Lomuto's.

Median-of-three (Mo3) Partition

Promoted by [Robert Sedgewick](https://en.wikipedia.org/wiki/Robert_Sedgewick_(computer_scientist)), the "median-of-three" scheme describes itself as choosing the median value among the first, last and middle elements of the array as the pivot.

It overcomes the problem of sorting almost sorted or reversely sorted arrays with a worst-case Ο(n2) by offering a relative "median" choice of an optimal pivot.

Randomized Partition

Quick Sort with a randomized partition is termed as the randomized QuickSort. It achieves an expected running time with an estimate of Ο(n ⋅ log n).

In the section of randomized algorithms, an algorithm of randomized selection is introduced and its principle is chosen as the foundation to build the pivot selection subroutine of randomized QuickSort.

Issues

Quick sort is sometimes effortless in sorting task; given an almost sorted array, it is a waste of code execution for too many comparisons and not to mention that pivot choosing takes time. And Insertion Sort is better in dealing with nearly sorted list.

Still, the quick sort scheme might inadvertently choose the least or most value of the sub-array in every recursion, resulting in a worst-case Ο(n2) comparisons. In other cases quick sort might be expecting to have efficiency of Ο(n ⋅ log n) given the medians of every sub-arrays are chosen in each iteration.

If there are duplicate elements in the array, or say elements with same value, standard quick sort routines won't work as brilliant as we expect. In a typical Dutch National Flag problem, a three-way partitioning routine is adopted to split the values into three groups: color of balls is red, color of balls is white and color of balls is black; Then, an improved QuickSort should look like:

QUICK_SORT(A, low, high)
  if low 

Algorithm Analysis

If every time the least or most value of sub-arrays been chosen as _pivot_s, the resulting complexity would be Ο(n2).

If every time the median value of the sub-array been chosen as pivot (best pivot), the resulting complexity would be Ο(n ⋅ log n). It still holds even if the pivot got chosen randomly in each run, what to be noted is there is no assumptions on data sets.

Proof:

Note: the master method is not applicable here given that the subproblems are unbalanced and unpredictable.

1. Define entry variable 𝓏i as the ith smallest element in the inputs.

2. Create an indicator random variable Xij = I{ 𝓏i compares 𝓏j }.
3. Then, the total number of entry comparisons:

1. Apply linearity of expectation,

wherein Pr(𝓏i compares 𝓏j) = Pr(𝓏i is chosen as the pivot) + Pr(𝓏j is chosen as the pivot) = 1 / (j-i+1) + 1 / (j-i+1) = 2 / (j-i+1)

1. Summing up terms separately, the asymptotic approximation is obtained,

complexity holds, proof ends.

Additional References

1. Why is quicksort better than other sorting algorithms in practice? https://cs.stackexchange.com/questions/3/why-is-quicksort-better-than-other-sorting-algorithms-in-practice