Quicksort in C++ with Tail Recursion

How does quicksort work?

There are some different versions of quicksort, we are going to look at the "vanilla" quicksort in this article. Observe the sequence: 7 4 8 3 9 1 2 6 5. We want to sort this sequence by using the quicksort method. We begin by picking a pivot element, the different versions of quicksort have different ways of choosing the pivot element, here it will always be the last element. What we want to do is to rearrange the sequence so every element that is greater than our pivot is to the right of the pivot, and every element that is smaller than the pivot to the left. This step is called partitioning.

To accomplish this, we are making use of a "counter" that goes from left to right, and a counter that goes from right to left. The left counter is going to look for elements that are greater than the pivot. When such an element is found, the counter to the right starts to look for elements less than the pivot. When that is found, the counters swap their elements, and the left counter starts again from where it left of. This proceeds until the two counters overlap. When they do that, the pivot element swaps with the position of the left counter. The pivot element is now in its right place, and need not to be included in a partition again.

Here's an illustration of this with the sequence above:

7 4 8 3 9 1 2 6 5   <-- 7 is greater than 5
^             ^ 
7 4 8 3 9 1 2 6 5   <-- 2 is less than 5, swap
^           ^    

2 4 8 3 9 1 7 6 5
  ^         ^  

2 4 8 3 9 1 7 6 5   <-- 8 is greater than 5
    ^       ^    

2 4 8 3 9 1 7 6 5   <-- 1 is less than 5, swap
    ^     ^  

2 4 1 3 9 8 7 6 5
      ^   ^  

2 4 1 3 9 8 7 6 5   <-- 9 is greater than 5
        ^ ^  

2 4 1 3 9 8 7 6 5   <-- The two counters overlapped, swap left with pivot
      ^ ^  

2 4 1 3 5 8 7 6 9   <-- The pivot is now in its correct spot
        *

The sequence can now be divided into two sequences, a sequence to the left of the pivot and a sequence to the right of the pivot. Those two sequences are partitioned as well, and this continues until the whole sequence is sorted.

 

Partition in C++

template <typename T>
T partition(std::vector<T>& arr, int left, int right) {
	int pivot = right;

	while (left < right) {
		while (arr[left] < arr[pivot] && left <= pivot) {
			left++;
		}

		while (arr[right] >= arr[pivot] && right > left) {
			right--;
		}

		if (left < right) {
			std::swap(arr[left], arr[right]);
			left++;
		}
	}

	std::swap(arr[left], arr[pivot]);
	return left;
}

Observe the code above. It takes a vector as an argument, and the two "counters" I talked about before. The rightmost element is chosen as the pivot, and a loop goes on until the left counter is greater than the right. Left counter goes up until it finds an element that is greater than or equal to the pivot, or until the left counter exceeds the pivots position. After that, the right counter goes down until an element that is less than the pivot is found, or until the right counter is less than the left counter. Then we swap the left and right elements, if the left counter is still less than the right counter. And when the loop is done, the left counters element swaps with the pivot element, and the left position is returned. It's a pretty straightforward implementation of the description before.

 

Naive implementation of Quicksort

template <typename T>
void quicksort(std::vector<T>& arr, int left, int right) {

	if(left < right) {
		int pivot = partition(arr, left, right);

		quicksort(arr, left, pivot - 1);
		quicksort(arr, pivot + 1, right);
	}
}

If we would continue with a straightforward implementation, it would look something like this. This works fine for a vector with few elements, but since every call to quicksort is added to the stack, a stack overflow is going to happen with a large vector. A solution to this problem is to implement tail recursion, or as it's also called, tail call optimization.

 

Quicksort with tail recursion / tail call optimization

template <typename T>
void quicksort(std::vector<T>& arr, int left, int right) {

	while (left < right) {
		int pivot = partition(arr, left, right);

		if (pivot - left <= right - pivot) {
			quicksort(arr, left, pivot - 1);
			left = pivot + 1;
		}
		else {
			quicksort(arr, pivot + 1, right);
			right = pivot - 1;
		}
	}
}

Here we use a while loop to reduce the number of recursive calls. The smaller sequence is always evaluated first. This solution will not guarantee that stack overflow won't occur, but it will make it a lot less likely. Call this function with a vector arr:

quicksort(arr, 0, arr.size()-1);