# Hoare's Quicksort Algorithm in Python - Animated Visualization with Code

The ultimate visualization and guide to learn Hoare's quicksort algorithm for efficient comparison based sorting

Hoare's Quicksort has been around since the early 1960s and is still one of the most popular and efficient sorting algorithms around.

Average time complexity: `O(n log n)`

Space complexity: `O(log n)` auxiliary*

*Notice in the animation below, we are swapping elements in place (no extra space), however, the call stack grows logarithmically.

Quicksort has two common implementation schemes:

1. Lomuto's partition scheme: Easier to understand and implement at the cost of worse performance
2. Hoare's partition scheme: The original version - harder to understand but more performant

## Quicksort visualized with animation

*As always, remember to pause and manually step-through the animation below if you want to thoroughly review the code highlights and annotations.

### Quicksort overview

The quicksort algorithm essentially functions as follows:

1. Quicksort sets the `low` and `high` partition indices
2. Pointer (`i`) travels from `low` up until `pivot` < `array[i]`
3. Pointer (`j`) travels from `high` back until `pivot` > `array[j]`
4. We return a new `pivot` position at `j` when `i` and `j` cross over
5. If `i` & `j` did not cross, then swap `i` and `j`

## Full quicksort code breakdown and guide

Here's our unsorted array that we will use throughout our guide below:

## unsorted array

40312213

First, we trigger our initial `quicksort` method with `low` at index `0` and `high` at the last item in our array:

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```
40312213

In our main quicksort method we check if low (`0`) is less than high (`len(array)-1`), then we run `partition` which is where the main sorting logic happens:

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```

Now we can start by initializing our 3 main index variables:

• `pivot` - the middle of our partition segment
• `i` - travels from `low` and increments forward
• `j` - travels from `high` and decrements backward

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```
40312213

Next, we create an infinite while loop that will run until the high and low indices crossover:

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```

Next, we increment `i` until our array's value at `i` is greater than or equal to `pivot`'s value:

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```
40312213

Since `array[i]` is already > `pivot`, we don't increment `i` at all.

Next, we decrement `j` until our array's value at `j` index is less than or equal to `pivot`'s:

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```
40312213

Since `array[j]` is already < `pivot`, we don't decrement `j`.

Next, check if `i` index position is greater than or equal to `j` index position. Once `i` and `j` crossover we need to create a new partition, so we return `j` before the swap happens.

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```
40312213

Since `i:0` is less than `j:3` we continue on to swap these two.

Finally, if `i` and `j` did not crossover then we swap them:

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```
10312243

Since `i` > `pivot`, this means that `i` needs to be move to the opposite side of `pivot`. Since `j` was less than `pivot`, that means `j` needs to move to the opposite side of `pivot`. So we simply swap the two.

After the swap, we continue our while loop:

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```
10312243

Remember we swapped our array items, so now i == 1, which means now array[i] is less than pivot's value. So we increment up 1 which means now `array[i]:3` is equal to `pivot:3` so we exit out of our first inner while loop.

Let's check `j`:

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```
10312243

We decremented until `j` < `pivot`

And again, check if `j` and `i` have crossed over. They haven't yet, so we can swap again:

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```
10213243

We swap `i` and `j` again since `j` was less than `pivot`.

At this point, we do have a fully sorted array, simply because our array is so short. However, our algorithm still has work to do.

After swapping the last two items, once again we loop through our infinite while loop.

This time we don't increment `i` since `pivot` and `i` are equal, we do decrement `j` since `array[j]:3` is greater than `pivot:2`:

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```

And again, we check if `i >= j` which is true, so now we `return j` which exits our while loop. Back in our main `quicksort` method we now have a new `pivot`:

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```

So, each quicksort partition works pointer `i` up and pointer `j` back, swapping when `i` or `j` are out of order from the `pivot`. When finally the two pointers meet/cross each other then `return j` which will be the high point of the next partition and the low point of the partition after that. Keep in mind each quicksort is recursive, so we could recursively run several additional partitions before the call stack pops back and allows `line 6` to run (you can see this happening in the animation at the top):

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```

## hoare_partition_quicksort

``````class Sort:
def _quicksort(self, array: list, low: int, high: int):
if low < high:
pivot = self._partition(array, low, high)
self._quicksort(array, low, pivot)
self._quicksort(array, pivot + 1, high)

def _partition(self, array: list, low: int, high: int) -> int:
pivot = array[(high + low) // 2]
i = low
j = high

while True:

while array[i] < pivot:
i += 1

while array[j] > pivot:
j -= 1

if i >= j:
return j

array[i], array[j] = array[j], array[i]

def sort(self, array: list) -> list:
self._quicksort(array, 0, len(array) - 1)
return array```
```

Further reading - includes details on Lomuto's partition variation as well: Wikipedia, Stanford