3 minute read

If we say that main idea of Merge sort is recursively merge, then the quick sort is just recursively partitioning.

                                           ___ MIT

1. Intuition

Let A be the array we want to sort. Firstly, we partition A into 3 sets:

  • Pivot set: A singleton set that only contains the pivot; (the pivot is usually the last element in the current array portion A[r])
  • Greater set: Contains the elements from A[i+1] to A[j - 1] which are all greater than the pivot;
  • Less & Equal set: Contain the elements from A[p] to A[i] which are all less and equal to the pivot.

$ Loop invariant (Three conditions):



$ Maintenance:


2. Pseudocode

-- choose the last item as the pivot --
algorithm QuikSort(array, start, end):
    if start < end then
        pivot_i = Partition(array, start, end)
        QuikSort(array, start, pivot_i-1)
        QuilSort(array, pivot_i+1, end)

function Partition(array, start, end):
    pivot = array[end]
    i = start - 1
    For j := start to (end-1) do
        if array[j]  pivot then
            i = i + 1 --> array[i] is included in the smaller-set so we need to increase it before the exchange 
            Exchange array[i] with array[j]
    Exchange array[i+1] with array[end]
    return i+1

Tips: What hapens if p == r?

If p == r, then A[j] == pivot and when i++, i = j = r so that the first exchange A[i] with A[j] operation will be useless and (i+1) in both second exchange operation and the return statement will cause array out of range.

3. Time Complexity

The running time of quicksort depends on whether the partitioning is balanced or unbalanced, which in turn depends on which elements are used for partitioning.

  • Balanced partitioning :≈ merge sort
  • Unbalanced partitioning :≈ insertion sort

(1) Unbalanced Partitioning (Worst case):

The worst-case behaviour for quicksort occurs when the partitioning routine produces one subproblem with n 1 elements and one with 0 elements.

\(T(n) = T(n-1) + T(0) + \Theta(n) \\ = T(n-1) + \Theta(n)\) Then, we can use subsitution method to prove that: \(T(n) = T(n-1)+\Theta(n) \\ = \Theta(n^2)\)

(2) Best Partitioning (Best case):

In the most even possible split, PARTITION produces two subproblems, each of size no more than n=2, since one is of size floor(n/2) and one of size (ceil(n/2)-1). In this case, quicksort runs much faster. \(T(n) = 2T(n/2) + \Theta(n)\) By case 2 of the master theorem (Theorem 4.1), this recurrence has the solution: \(T(n) = \Theta(nlgn)\)

(3) Balanced Partitioning (Average case)

Any split of constant proportionality yields a recursion tree of depth Θ(lgn) where the cost at each level is O(n)

The running time is, therefore, O(nlgn) whenever the split has constant proportionality


Tips: Intuition for average-case

  • For a random input array, the partitioning is different at every level;
  • The average-case ≈ a mix of “good” and “bad” partitioning (good: constant proportionality; bad: unbalanced);
  • The “good” and “bad” splits are distributed randomly through the tree.
  • The depth of the tree is always O(lgn) and O(n) work is performed at each level.

1aa0115f8598f8190f8a7f6160bbda87.png (bad+good ≈ good)


// Scala
object QuickSortAlgo {

    def quickSort(array: Array[Double], start: Int, end: Int): Unit = {
        if (start < end) {
            var pivot_i = partition(array, start, end)

            quickSort(array, start, pivot_i-1)
            quickSort(array, pivot_i+1, end)

    def partition(array: Array[Double], start: Int, end: Int): Int = {
        var pivot = array(end)
        var i = start - 1

        for (j <- start until end) {
            if (array(j) < pivot) {
                i += 1
                // swap
                var tmp = array(i)
                array(i) = array(j)
                array(j) = tmp
        var tmp = array(i+1)
        array(i+1) = array(end)
        array(end) = tmp

        return i+1

    def main(args: Array[String]): Unit = {
        var array = Array(4234,234234,23,234,-134,4123,41,578,-342,55,0.2323,0.325)
        println("\nBefore sorting:")
        println(array.deep.mkString(" "))

        quickSort(array, 0, array.length-1)

        println("\nAfter sorting:")
        println(array.deep.mkString(" "))
# Python
def partition(array, start, end):
    pivot = array[end]
    i = start - 1

    for j in range(start, end):
        if array[j] <= pivot:
            i += 1
            array[i], array[j] = array[j], array[i]

    array[i+1], array[end] = array[end], array[i+1]

    return i+1

def quick_sort(array, start, end):
    if start < end:
        pivot_i = partition(array, start, end)

        quick_sort(array, start, pivot_i-1)
        quick_sort(array, pivot_i+1, end)

if __name__ == "__main__":
    array = [4234,234234,23,234,-134,123,41,578,-342,55,0.9323,0.325]
    # array = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

    print("Before sorting: ", array)
    quick_sort(array, 0, len(array)-1)
    print("After sorting:  ", array)

Leave a comment