# Quick Sort

Tony Hoare developed this algorithm when he was a visiting student at Moscow State University. It selects a pivot, partitions the array into two, and repeats this process recursively. It’s alternatively called the partition-switcher algorithm for this reason.

# UCL version

- Shuffle the array first to randomly distribute the elements
- Partition the array and get the index of the pivot
- Repeat the partition

## Partition

`i`

wants to find the elements larger than the pivot while `j`

wants to find smaller elements. And you swap them.

def partition(arr, lo, hi):

i = lo + 1

j = hi

while (True):

while (arr[i] <= arr[lo] and i < hi):

i += 1

while (arr[lo] <= arr[j] and lo < j):

j -= 1

if (j <= i):

break

# swap (i, j)

temp = arr[i]

arr[i] = arr[j]

arr[j] = temp # swap (j, lo)

temp = arr[j]

arr[j] = arr[lo]

arr[lo] = temp

return j

## Time Complexity

**Average Case**It’s O(N logN) when the elements are distributed well so that you can partition the array into two every time.

**Worst Case**What if the array is already sorted in ascending order?

`i`

doesn’t move since it already found a larger element. `j`

, however, keeps moving towards the left until it reaches the beginning where the pivot it. In this case, we change nothing. `j = 0`

. This means that we have to repeat this process for the array whose `lo = j+1`

and `hi=hi`

. Thus, the time complexity is O(N²/2).

# Some improvements

## Using an insertion sort when N < 10

It’s rather inefficient to use recursion for small numbers. Especially when you should run it multiple times.

## Quicksort with 3-way partition

If there is only one slot for a pivot, it’d be quite inefficient if the array has a lot of duplicated elements.

So here comes 3-way QuickSort. In this way, we don’t have to reiterate through the same elements, and thus reduce the total number of recursion levels.