Literate Quicksort

This post is a literate program, it both explains and implements quicksort. Quicksort is a fast, recursive sorting algorithm. The big idea is to take an array of \( n \) unsorted integers, choose a pivot element, and then recursively sort the two arrays on either side of the pivot.

Once a pivot is selected, every number to the left of the pivot is smaller, and every one to the right is bigger. This pivot selection process is called partitioning, since it creates two partitions which can be sorted independently. The pivot is already in it’s final sorted place.

Here’s an example of partitioning, I made this animation from these excellent slides from Tulane university:

At the end of the partitioning step, the variable i points to the pivot, everything to the left is less than 6, and everything to the right is bigger than 6. Now the pivot is in it’s final sorted position, and the left and right sub-arrays can be sorted independently. At this point, we can make two recursive calls on the left and right sub-arrays.

quicksort(numbers, start, pivot); // sort left sub-array
quicksort(numbers, pivot, end);   // sort right sub-array

This will create a binary tree of recursive function calls, until it bottoms out at sub-arrays with 0 or 1 element in them. That base case is handled by a conditional that only recurses if end - start > 2:

void quicksort(int numbers[], int start, int end) {
  if(end - start > 2) {
    int pivot = partition(numbers, start, end);
    <<<recurse>>>
  }
}

Define the partition function

In order to make the partition step fast, we want to avoid shifting the whole array around. A good way to do this is to swap elements in place.

void swap(int *a, int *b) {
  int temp = *a;
  *b = *a;
  *a = temp;
}

Now to the partition function, the i variable will be the upper bound of the left partition. The j variable will be the upper bound of the right partition. The pivot will be stored in the last position of the array, at index n-1. The region between j and (n-1)-1 is the unprocessed part of the array.

int partition(int numbers[], int start, int end) {
  int pivot = numbers[end];
  int i = start-1;
  for(int j = start; j < end-1; j++) {
    if(numbers[j] <= pivot) {
      i += 1;
      swap(&numbers[j], &numbers[i]);
    }
  }
  swap(&numbers[i+1], &numbers[end]); // Move pivot to between left and right
}

Define the input and read in unsorted numbers

Let’s name array to be sorted: numbers. Let n be the size of the unsorted array. For this program, I generated a list of 1,000,000 unsorted integers in this file: unsorted_integers.txt, they are newline-delimited. This code block defines the parameters and reads all the million integers into the numbers array.

int n = 1000000;
int numbers[n];
FILE *file = fopen("unsorted_integers.txt", "r");
for(int m = 0; m < n; m++) {
  fscanf(file, "%d\n", &numbers[m]);
}
fclose(file);

The main program

#include <stdio.h>  // for printf
#include <stdlib.h> // for FILE

<<<swap function>>>

<<<partition function>>>

<<<quicksort function>>>

int main(int argc, char *argv[]) {
  <<<read in unsorted numbers>>>
  return 0;
}