Published in

lukeleeai

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

1. Shuffle the array first to randomly distribute the elements
2. Partition the array and get the index of the pivot
3. 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.

--

--