QuickSort Explained

In this post, let's have a quick look at how Quick Sort works.

Let's take the following example:

4 2 6 5 3

Quick sort works by finding the correct position (the partition index) for the pivot element.

Thereby partitioning the array into two parts: a) unsorted parts before the partition index and b) unsorted parts after the partition index.

The item at the partition index would be at the correct position. Therefore we would simply run the algorithm again recursively for the unsorted parts to get the desired result of a complete sorted array.

Let's see this with the help of an example.

Partitioning

Step 1 - Choose A Pivot

To sort it using the Quick Sort, we'll first need to choose a "pivot" item. Let's choose the last item "3" as "pivot".

4 2 6 5 [3]

Step 2 - Choose A Partition Index

Now we choose a partition index called "pIndex". Let that be the first item in the given array (4 in this case).

Then we loop through the array (excluding pivot), comparing current item with pivot, and swapping with pIndex when the condition currentItem <= pivot is True.

4 2 6 5 [3]
p
^

Is 4 <= 3 ? No.

4 2 6 5 [3]
p
  ^

Is 2 <= 3 ? Yes. Swap with pIndex and increment pIndex.

2 4 6 5 [3]
  p
    ^

Is 6 <= 3 ? No.

2 4 6 5 [3]
  p
      ^

Is 5 <= 3 ? No.

Step 3 - Swap pIndex With Pivot

After going through the first loop, we found the correct position (the partition index) for our pivot item.

Swap the item at pIndex with Pivot and return pIndex.

2 [3] 6 5 4
   p

Step 4 - Recursively Sort Unsorted Parts

This means we'll need to run QuickSort again on the unsorted parts as follows:

quickSort(array, start, pIndex-1)
quickSort(array, pIndex+1, end)

Step 5 - Dry run of the recursion

Currently, we have the following array:

2 [3] 6 5 4

The left part only has one item 2 so it is already sorted. Only the right part needs to be sorted.

Let's do that by following the steps 1 to 4.

1. Choose the last item "4" as the pivot.

2. Choose the first item "6" as the pIndex.

2a. Go through the array excluding the pivot and swap where we find an item less than the pivot.

This is to make sure:

• all the items on the left of pIndex are less than or equal to the pivot.
• and all the items on the right are greater than the pivot.

6 5 [4]
p
^

Is 6 <= 4 ? No.

6 5 [4]
p
  ^

Is 5 <= 4? No.

Loop ends.
Swap item at pIndex with Pivot.
Return pIndex.

[4] 5 6
 p

4 is at the right place.
Unsorted numbers are 5 and 6.

Following step 4, recursively sort the unsorted parts.

Recursion would help us discover that 5 and 6 are already at their correct positions.

Therefore the array is already sorted:

2 3 4 5 6

The Code

The code should be fairly easy to read, especially after test case explained above.

def quicksort(arr, start, end):

  if start >= end:
    return

  pIndex = partition(arr, start, end)
  quicksort(arr, start, pIndex-1)
  quicksort(arr, pIndex+1, end)

  return arr

def partition(arr, start, end):

  pivotIndex = end
  pIndex = start

  for i in range(start, pivotIndex): # excluding pivotIndex
    if arr[i] <= arr[pivotIndex]:
      arr[i], arr[pIndex] = arr[pIndex], arr[i]
      pIndex += 1

  arr[pIndex], arr[pivotIndex] = arr[pivotIndex], arr[pIndex]
  return pIndex

If you have a difficult time understanding it, just take the above example and perform a dry run on a piece of paper. It is the fastest way to learn and absorb a new concept!

FAQ

(1) What's the average case complexity?

Time: O(n log n)
Space: O(log n)

(2) What's the worst case complexity?

Time: O(n^2)
Space: O(n)

(3) What would be the worst case?

When the array is already sorted. Why? because each loop in each recursive call would touch every single item.

The n recursive calls would take O(n) space. Also, n recursive calls, each running a for loop that has n iterations would result in O(n^2) time complexity.

(4) What's the difference between Quick Sort and Merge Sort?

Quick Sort algorithm doesn't require any extra storage, Merge sort requires extra storage space to store the auxiliary array.