Quicksort in C

Introduction

Quicksort is one of the most common sorting algorithms and one of the most efficient. It’s so common that it’s part of C89. That said, it’s still good to know how it works, its strengths, and it’s weaknesses.

It takes as a divide and conquer approach to sorting. An element is selected as a pivot point. The elements are sorted against the pivot so all elements less than the pivot are on the left side and greater than elements are on the right. Functionally, we have two sub arrays based on the pivot. Each sub array has the same pivot and sort operation applies. This is repeated until the each sub array is 1 element. At this point, no further sorting is possible and the array is sorted.

Example to illustrate the process.

    array: [1 9 3 5 8 2 4]
    pivot = 4

    arrays: [1 3 2]   [4]   [5 9 8]
    piviot = 2            pivot = 8

    arrays: [1]  [2]  [3]  [4]  [5]  [8]  [9]

    array: [1 2 3 4 5 8 9]

Big-O complexity:

Best Average Worst
Time O(n log n) O(n log n) O(n^2)
Space O(log n)

This is a non-stable, in place algorithm.

Prerequisites

One thing we’ll need to implement Quicksort is a swap function.

Partitioning

There are multiple partition schemes for splitting the array into parts. Each one has differences in complexity to implement as well as efficiency.

Hoare Partition Scheme

This is the original scheme from the author of Quicksort and it has good performance.

For this method we will use the first and last elements to determine the pivot. They are moved toward each other until each reaches a point that is greater and less than (on the wrong side) the pivot. What’s the pivot? It’s the point where they cross! As they move if they find a value on the wrong size of the pivot it will be swapped.

static void quick_sort(void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *))
{
	void   *pivot;
	size_t  left;
	size_t  right;

	if (base == NULL || nel < 2 || width == 0 || cmp == NULL)
		return;

	pivot = base;

	left  = 0;
	right = nel-1;
	while (left < right) {
		while (cmp(base+(left*width), pivot) < 0 && left 0 && left<right) {
			right--;
		}
		if (left < right && cmp(base+(left*width), base+(right*width)) != 0) {
			/* Track the pivot value. The pivot is stored as a pointer
			 * but the value itself will be swapped. Update the pivot
			 * pointer so the value does not change on subsequent comparisions. */
			if (base+(left*width) == pivot) {
				pivot = base+(right*width);
			} else if (base+(right*width) == pivot) {
				pivot = base+(left*width);
			}
			swap(base+(left*width), base+(right*width), width);
		} else {
			left++;
		}
	}

	quick_sort(base, left-1, width, cmp);
	quick_sort(base+(left*width), nel-left, width, cmp);
}

The two indexes move independently and will not necessarily meet in the middle. Each will move toward the middle until it encounters a value that is on the wrong side of the pivot. If both find such a value they are swapped and indexes will start moving again. If the indexes meet (or cross) the pivot has been found. The array is split into its two sub arrays at this index.

Keep in mind, the pivot is _not_ an index, it is a value. Thus the value itself needs to be tracked. Since we know the width we could use a `malloc`ed temporary variable to store a copy of the value. However, that would be wasteful. Instead we track the pointer to the pivot value and update it if it is swapped into a new index. Remember that `swap` will swap the bytes at a pointer location not the pointer itself. So we need to change the pointer we are tracking to the one with the pivot value.

Lomuto Partition Scheme

This scheme as developed as a simpler alternative to the original Hoare scheme. However, while easier to implement, it has worse performance.

We’re going to use the last element as the pivot point and the index will not be part of the comparison. Think of it like the last index is being used as a temporary to hold the pivot value. Once comparison has finished the last element will be inserted back into the array at the appropriate place.

static void quick_sort(void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *))
{
	void   *pivot;
	size_t  hi;
	size_t  i;
	size_t  j;

	if (base == NULL || nel < 2 || width == 0 || cmp == NULL)
		return;

	hi    = nel-1;
	pivot = base+(hi*width);

	for (i=0, j=0; j<hi; j++) {
		if (cmp(base+(j*width), pivot) <= 0) {
			/* Don't swap an element with itself. */
			if (j != i) {
				swap(base+(i*width), base+(j*width), width);
			}
			i++;
		}
	}

	/* Swap the pivot (last element) into the array where all elements
	 * before are less than and after is greater than. */
	if (i < hi)
		swap(base+(i*width), base+(hi*width), width);

	quick_sort(base, i, width, cmp);
	quick_sort(base+((i+1)*width), nel-i-1, width, cmp);
}

Two indexes are tracked with `i` and `j`. Where `i` is the index where the pivot will be inserted. `j` iterates though all elements. If `j` encounters an element greater than or equal to the pivot, the element's value is swapped into `i` and `i` is incremented.

Once all elements (except the last because this is the pivot) are checked, the pivot is swapped into index `i` which is the first value greater than the pivot.

Pivot selection

While any pivot will sort the array, the pivot value is very important. Sorted or mostly sorted arrays can quickly degraded to worst case performance with a bad pivot. There are a number of pivot selection schemes which are better than always using the first and last elements. Some examples:

  • Random index.
  • Middle index.
  • The median of first middle and last (“median-of-three”).

Typically, the pivot index will be in a separate function from the main quick_sort function but this is not required. It does make the implementation cleaner due to separating logical operations. It also makes it easier to replace the pivot selection function. Conversely, it does make it harder to understand the algorithm.

Optimization

What I have here are two basic implementations of Quicksort and while they are functional they aren’t very performant. Sorting is an intensive processes so these should be used for educational purposes only.

An optimized implementation (that is the basis of the BSD qsort implementation) can be found in the paper “Engineering a Sort Function” by Jon L. Bentley and M. Douglas McIlroy. It was published in Software—Practice and Experience vol. 23(11), 1249–1265 (November 1993). I highly recommend reading this in order to understand how to optimize qsort.