# Day 57: Quicksort

It took me almost two months to find a courage to implement quicksort. And here we are. This algorithm is a nightmare. It’s pretty easy to grasp the concept, but it’s extremely difficult to implement.

I have already implemented another algorithm based on the same idea on day 35, but I cowardly duplicated partitions.

Quicksort is a very efficient algorithm running in expected O(n.log n) time, with very low multiplicative constant, around 2 — if implemented correctly.

The problem is, standard version of the algorithm is linearithmic only on unique data. If elements occur many times, the performance degrades. Lifesaver is 3-way quicksort that splits the data into three partitions, lower, higher and same as pivot.

Another catch is uniform randomization of pivot. It is a vital part of proof that the algorithm is expected to run in linearithmic time. Deterministic selections of pivot do not have this property.

https://github.com/coells/100days

https://notebooks.azure.com/coells/libraries/100days

#### algorithm

`def swap(data, i, j):    data[i], data[j] = data[j], data[i]`
`def qsort3(data, left, right):    # sorted    if left >= right:        return`
`    # select pivot    i = np.random.randint(left, right + 1)    swap(data, left, i)    pivot = data[left]`
`    # i ~ points behind left partition    # j ~ points ahead of right partition    # k ~ current element    i, j, k = left, right, left + 1`
`    # split to [left] + [pivot] + [right]    while k <= j:        if data[k] < pivot:            swap(data, i, k)            i += 1        elif data[k] > pivot:            swap(data, j, k)            j -= 1            k -= 1        k += 1`
`    # recursion    qsort3(data, left, i - 1)    qsort3(data, j + 1, right)`
`def qsort(data):    qsort3(data, 0, len(data) - 1)`

#### run

`> data = np.random.randint(0, 10, 100)> print(data)`
`[9 9 6 3 1 4 7 1 4 8 0 3 9 7 9 1 0 9 9 5 4 2 4 2 7 6 6 1 7 3 1 1 3 6 8 6 4 5 3 1 5 9 3 2 0 2 2 6 9 9 0 6 2 8 2 9 2 6 8 6 6 7 6 5 8 9 0 9 9 4 3 9 6 9 5 9 1 0 3 2 1 0 9 4 6 3 4 0 8 9 8 9 5 7 4 2 9 5 0 5]`
`> qsort(data)> print(data)`
`[0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9]`