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]
Show your support

Clapping shows how much you appreciated Tomáš Bouda’s story.