We want to sort an array with $n$ elements. Quick-sort does this by breaking up the array into non-overlapping segments, sorting them separately and then combining the results.

For instance, suppose we have a box with slips of paper with numbers between 100 and 300 to be sorted. We could first separate the slips into two bunches: those with values below 200 and those with values above 200. We can sort these bunches separately. Since all the values in the second bunch are larger than those in the first bunch, we can combine them easily into a single sorted bunch. (See Sorting | Online Study Material - IARCS for a great resource on this.)

Algorithm with Example

The video focuses purely on the algorithm and doesn’t get distracted by implementation details, which is great if you’re trying to understand the algorithm for the first time.

Algorithm Steps

We’re given an array of length $n$. (steps below assume that all elements in the array are distinct)

def quick_sort(array)
    pivot = randomly chosen element from the array
    left = all elements smaller than pivot
    right = all elements larger than pivot
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [pivot] + right

Since the algorithm is recursive (quick-sort calls quick-sort for smaller arrays), we need to have a base case. The base case for quick sort is that if the array is of length 1, then it is already sorted.

Implementation

Following is the implementation of quick sort in C++.

#include <bits/stdc++.h>
using namespace std;
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);        // Index of smaller element
    for (int j = low; j < high; j++)
    {
        /* 
          If current element is smaller than or
          equal to pivot
        */
        if (arr[j] <= pivot)
        {
            i++;              // increment index of smaller element
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {  
        int p= partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }
}
int main()
{
    int size = 9;
    int arr[] = {5, 10, 8, 7, 3, 6, 12, 2, 7};
    quickSort(arr, 0, size);
    cout << "Sorted array:\n";
    for (int i=0; i < size; i++)
    cout << arr[i] << " ";
    return 0;
}

Following is the implementation of quicksort in python:

def partition (arr, low, high):
    pivot = arr[high];    # pivot
    i = (low - 1)         # Index of smaller element
    for j in range (low, high):
        #If current element is smaller than or
        # equal to pivot element
        if arr[j] <= pivot:
            #increment index of smaller element
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return (i + 1)
def quicksort(arr, low, high):
    if low < high: 
        p = partition(arr, low, high)
        quicksort(arr, low, p - 1)
        quicksort(arr, p + 1, high)
arr = [5, 10, 8, 7, 3, 6, 12, 2, 7]
quicksort(arr, 0, len(arr)-1)
print("Sorted array:")
print(arr)

Comparison to Simple Sort

Naive sorting algorithms such as Simple Sort in the previous tutorial are take O($n^2$) time because they duplicate comparisons. If we have $n$ numbers, then the total number of pairs is $n(n-1)/2$ = O($n^2$), and naive sorting algorithms compare every pair of numbers.

In quick-sort, we choose a pivot and separate the array into two parts. Once we separate the two parts, we know that every number in the first part is lesser than every number in the second part without ever having compared them directly to each other.

Bonus: An animated race between bubble-sort (similar to simple-sort) and quick-sort!

Bonus: Performing the partition in-place

It is possible to run quick-sort in-place. That is, we do not need to make separate arrays which store each part. This saves memory and also makes the code faster. The first 2 minutes of the video below describe how to perform in-place partition.

In addition, you can also check-out the pseudo-code for performing in-place partition on Wikipedia.

Comparison to merge-sort (and run-time analysis)

The main advantage of quick-sort over merge sort, is that the sorting can be done in-place. This saves time because we don’t have to create new arrays.

The run-time of quick-sort is same as merge-sort in the average case, i.e. O($n \log n$). This is true even if we get quite bad splits of the array (say 10% on one side and 90% on the other side) each time.

The main disadvantage is that is the randomly picked pivot is bad for the first few times, then it will still take longer to execute.

Also, for those who are theoretically inclined, the algorithm has a worst-case complexity of O($n^2$), although that is almost impossible if sorting more than 10 elements.