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 sortingHoare'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:
- Lomuto's partition scheme: Easier to understand and implement at the cost of worse performance
- Hoare's partition scheme: The original version - harder to understand but more performant
For this article, we will learn Hoare's original version.
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:
- Quicksort sets the
lowandhighpartition indices - Pointer (
i) travels fromlowup untilpivot<array[i] - Pointer (
j) travels fromhighback untilpivot>array[j] - We return a new
pivotposition atjwheniandjcross over - If
i&jdid not cross, then swapiandj
Full quicksort code breakdown and guide
Here's our unsorted array that we will use throughout our guide below:
unsorted array
We start with this unsorted array
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
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 segmenti- travels fromlowand increments forwardj- travels fromhighand 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
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
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
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
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
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
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
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
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
