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.
- Shuffle the array first to randomly distribute the elements
- Partition the array and get the index of the pivot
- Repeat the 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 (arr[i] <= arr[lo] and i < hi):
i += 1
while (arr[lo] <= arr[j] and lo < j):
j -= 1
if (j <= i):
# 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
It’s O(N logN) when the elements are distributed well so that you can partition the array into two every time.
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).
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.