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.
