Quick sort

Algorithm

def quick(a):
    """
    Implements the quick sort algorithm.
    """

    def sort(a,low,high):
        if high <= low:
            return

        j = partition(a,low,high)
        sort(a,low,j-1)
        sort(a,j+1,high)

    def partition(a,low,high):
        pivot = a[low]
        i = low+1
        j = high
        while True:
            while a[i] < pivot and i < high:
                i = i + 1
            while pivot < a[j] and j > low:
                j = j - 1
            if i >= j:
                break
            temp = a[i]
            a[i] = a[j]
            a[j] = temp

        temp = a[low]
        a[low] = a[j]
        a[j] = temp

        return j

    sort(a, 0, len(a)-1)
    return a

Step by step

array = [1,0,3,4,2,5]

sort(array, 0, 5)
    partition(array, 0, 5)      | array = [0,1,3,4,2,5]
    sort(array, 0, 0)
    sort(array, 2, 5)
        partition(array, 2, 5)  | array = [0,1,2,3,4,5]

We will now see in detail the calls to the partition function.

partition(a, 0, 5)
------------------

a = [1,0,3,4,2,5]
low = 0
high = 5

pivot = a[0] | pivot = 1
i = 1
j = 5
while True
    while a[1] < 1 and 1 < 5 | False
    while pivot < a[5] and 5 > 0 | pivot < 5 | True
        j = j - 1 | j = 4
    while pivot < a[4] and 5 > 0 | pivot < 5 | True
        j = j - 1 | j = 3
    while pivot < a[3] and 5 > 0 | pivot < 5 | True
        j = j - 1 | j = 2
    while pivot < a[2] and 5 > 0 | pivot < 5 | True
        j = j - 1 | j = 1
    while pivot < a[1] and 5 > 0 | pivot < 5 | False
    i >= j | 1 >= 1 | True

temp = a[0]
a[0] = a[1]
a[1] = temp     | a = [0,1,3,4,2,5]

return 1

partition(a, 2, 5)
------------------

a = [1,0,3,4,2,5]
low = 2
high = 5

pivot = a[2] | pivot = 3
i = 3
j = 5

while True
    while a[3] < 3 and 3 < 5 | False
    while 3 < a[5] and 5 > 2 | True
        j = j - 1 | j = 4
    while 3 < a[4] and 4 > 2 | False
    i >= j | 3 >= 4 | False
    temp = a[3]
    a[3] = a[4]
    a[4] = temp     | a = [0,1,3,2,4,5]

    while a[3] < 3 and 3 < 5 | True
        i = i + 1 | i = 4
    while a[4] < 3 and 3 < 5 | False
    while 4 < a[4] and 4 > 2 | True
        j = j - 1 | j = 3
    while 4 < a[3] and 3 > 2 | False
    i >= j | 4 >= 3 | True

temp = a[2]
a[2] = a[3]
a[3] = a[2]     | a = [0,1,2,3,4,5]

Complexity analysis

Time

Worst-case

The worst-case happens when the pivot is, in every recrsive call, the biggest (or the smallest) element. When this happens, for the first call we go through N elements, for the second call we go through N - 1 elements and for the last call we go through 2 elements. This is: N + (N - 1) + (N - 2) + … + 2.

So the cost is: O(N) = N²

Best-case

The best-case happens when the pivot is, in every recursive call, the middle of the rest of elements. When this happens, we are splitting in two the size of the array in every call.

So the cost is: O(N) = N · log N

Average case

Average case: O(N) = 2N · ln N = 2N · (log N / log e) = (2N / log e) · log N ≈ 1.39N log N.

Space

Each call to either partition or sort` uses a few variables. Since there will be log N calls the amount of space it takes is:

O(N) = N + log N.

Use cases

This algorithm is useful for sorting big arrays with not a lot of repeated elements.