# Quick Sort

Developed by [Tony Hoare](https://en.wikipedia.org/wiki/Tony_Hoare) early in 1950s, Quick Sort follows the [DnC](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-2/broken-reference) pattern but without the COMBINE phase in common DnC paradigm.

*An animated example:* [**Quick Sort Animation**](https://en.wikipedia.org/wiki/Quicksort#/media/File:Sorting_quicksort_anim.gif)

## 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](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-2/merge-sort), [Quick Sort](#quick-sort) is implemented in a style of [*sort-in-place*](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-2/broken-reference) with little extra memory usage. [Quick Sort](#quick-sort) is prevalent in many practical applications and its [average-case](https://cs-notes.gitbook.io/algorithm-notes/outline/asymptotic-analysis) running time Ο(n ⋅ log n) equates many of existing performant comparison-based implementations like [MergeSort](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-2/merge-sort).

Different partition methods incur distinct expected running time in total. It is widely adopted to use [randomized partition](#randomization-partition.md) 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*](#median-of-three-partition) *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](#quick-sort) yet less efficient than [Hoare Partition](#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](https://academic.oup.com/comjnl/article-lookup/doi/10.1093/comjnl/5.1.10) 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](https://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto) 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](https://cs-notes.gitbook.io/algorithm-notes/outline/asymptotic-analysis) Ο(n2) by offering a relative "median" choice of an optimal *pivot*.

### Randomized Partition

[Quick Sort](#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**](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-1/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](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-2/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](https://cs-notes.gitbook.io/algorithm-notes/outline/asymptotic-analysis) Ο(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](https://en.wikipedia.org/wiki/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](#quick-sort) 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*](https://cs-notes.gitbook.io/algorithm-notes/outline/overview/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](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-2/quick-sort) *X*ij = I{ 𝓏i compares 𝓏j }.
3. Then, the total number of entry comparisons:

![](https://204822229-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LQpLOTVKDY3pIvuIk2h%2F-LQpLtuWuWX31O5763zE%2F-LQpLvzGNM9SVBGeMm5I%2Fquick_sort_proof_1.jpg?generation=1541714732204484\&alt=media)

1. Apply [linearity of expectation](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-2/quick-sort),

![](https://204822229-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LQpLOTVKDY3pIvuIk2h%2F-LQpLtuWuWX31O5763zE%2F-LQpLvzIPHHU_ymbHSAJ%2Fquick_sort_proof_2.png?generation=1541714733080391\&alt=media)

![](https://204822229-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LQpLOTVKDY3pIvuIk2h%2F-LQpLtuWuWX31O5763zE%2F-LQpLvzKP3yWn5ShzMxp%2Fquick_sort_proof_3.png?generation=1541714732339952\&alt=media)

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](https://cs-notes.gitbook.io/algorithm-notes/outline/asymptotic-analysis) is obtained,

![](https://204822229-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LQpLOTVKDY3pIvuIk2h%2F-LQpLtuWuWX31O5763zE%2F-LQpLvzMKMIpNF8IrNRA%2Fquick_sort_proof_4.jpg?generation=1541714732608809\&alt=media)

![](https://204822229-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LQpLOTVKDY3pIvuIk2h%2F-LQpLtuWuWX31O5763zE%2F-LQpLvzOhPcGd77RsYxE%2Fquick_sort_proof_5.png?generation=1541714732858231\&alt=media)

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>
