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