# 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]