Taking apart Quicksort algorithm
Quicksort is a curious algorithm. Many people learn it soon after the bubble sort because it can be easy to understand and code. Despite this, quicksort is widely used. For instance, Java comes with a dual-pivot implementation to sort arrays. Here, I want to dissect it step by step to cement my knowledge.
Introduction
The idea of quicksort was described by its author, Tony Hoare, in The Computer Journal, Volume 5, Issue 1, 1962, Pages 10–16:
The method is based on the principle of resolving a problem into two simpler subproblems. Each of these subproblems may be resolved to produce yet simpler problems. The process is repeated until all the resulting problems are found to be trivial. These trivial problems may then be solved by known methods, thus obtaining a solution of the original more complex problem.
His version still stands, although here we're going to discuss a slightly shorter implementation, which is also easier to grasp. It's based on the Lomuto partition scheme. Various modifications of the original quicksort algorithm exist, such as the aforementioned dual-pivot version. Therefore, it can be said that quicksort today is a family of closely related algorithms rather than a specific algorithm.
Quicksort selects one element from an input array, known as the pivot element. The other elements are then rearranged around the pivot element as follows:
- Values less than the pivot element are placed to the left.
- Values equal to or greater than the pivot element are placed to the right.
Select the pivot element:
[4, 8, 7, 3, 6]
|- let's say this is the pivot element
Rearrange elements around it:
[4, 3, 6, 8, 7]
|- the pivot element is now in its sorted position
All elements are in correct segments concerning their relationship to 6, and vice versa.
4 and 3 < 6 -- left segment
8 and 7 > 6 -- right segment
Nonetheless, the array isn't fully sorted yet. To place the remaining values in their correct positions, the process starts again. This time, two arrays have to be sorted: one with values [4, 3], another with values [8, 7]. For each of these subarrays, a pivot point is selected, and values are sorted around it.
Sort subarrays to the left and right of the pivot point:
6
/ \
[4, 3] [8, 7]
|- |- 3 and 7 are the pivot elements for their respective arrays
Move values that are greater than the pivot point to the right:
[3, 4] [7, 8]
There's nothing left to sort. The full array is:
[3, 4, 6, 7, 8]
Even though the input array can be enormous, with each step, subarrays become smaller and smaller, and eventually, there will be no more elements to split them - just like in the example above. By that time, all pivot elements will be in correct positions, and the array will be sorted.
This approach significantly reduces the average run time compared to bubble, selection and insertion sorts. I executed some tests to demonstrate that:
Benchmark (totalElements) Mode Cnt Score Error Units
SortingAlgorithmsBenchmark.testBubbleSort 100 avgt 25 2239.672 ± 31.415 ns/op
SortingAlgorithmsBenchmark.testBubbleSort 300 avgt 25 20047.488 ± 458.636 ns/op
SortingAlgorithmsBenchmark.testBubbleSort 500 avgt 25 55059.188 ± 534.719 ns/op
SortingAlgorithmsBenchmark.testBubbleSort 700 avgt 25 113408.375 ± 1071.225 ns/op
SortingAlgorithmsBenchmark.testBubbleSort 900 avgt 25 214994.530 ± 772.172 ns/op
SortingAlgorithmsBenchmark.testQuickSort 100 avgt 25 655.788 ± 14.417 ns/op
SortingAlgorithmsBenchmark.testQuickSort 300 avgt 25 3178.036 ± 143.443 ns/op
SortingAlgorithmsBenchmark.testQuickSort 500 avgt 25 7021.062 ± 138.098 ns/op
SortingAlgorithmsBenchmark.testQuickSort 700 avgt 25 12938.110 ± 114.698 ns/op
SortingAlgorithmsBenchmark.testQuickSort 900 avgt 25 20931.144 ± 224.614 ns/op
The difference is stark, yet the number of elements is modest. This trend persists when sorting an array with hundreds of thousands or millions of items. These large numbers aren't in the chart because my computer couldn't complete the benchmarking overnight. The bubble sort took 14 minutes to sort an array with 16^5 = 1,048,576 elements! In contrast, quicksort handles this amount of data within a second. If you're interested in a deeper analysis, you can find it here.
The key difference between various versions of quicksort lies in how they select the pivot element and rearrange the other elements around it. We're going to use this implementation:
public class QuickSort {
private final Logger logger = LogManager.getLogger();
private final int[] array;
public QuickSort(int[] array) {
this.array = array;
}
public void sort() {
sort(0, array.length - 1);
}
private void sort(int leftIndex, int rightIndex) {
logger.info(format("%n=====%n=> Sorting %s", Arrays.toString(Arrays.copyOfRange(array, leftIndex, rightIndex + 1))));
if (leftIndex < rightIndex) {
logger.info(format("LeftIndex(%d) < rightIndex(%d), splitting into partitions", leftIndex, rightIndex));
int pivotIndex = partition(leftIndex, rightIndex);
sort(leftIndex, pivotIndex - 1);
sort(pivotIndex + 1, rightIndex);
} else {
logger.info(format("LeftIndex(%d) >= rightIndex(%d)", leftIndex, rightIndex));
}
}
private int partition(int leftIndex, int rightIndex) {
int i = leftIndex - 1;
int pivotValue = array[rightIndex];
logger.info(format("%nSorting partition from leftIndex(%d) to rightIndex(%d)", leftIndex, rightIndex));
logger.info(format("Taking the rightmost value (array[%d]=%d) as the pivot value", rightIndex, pivotValue));
for (int j = leftIndex; j < rightIndex; j++) {
if (array[j] < pivotValue) {
logger.info(format("Array[j](%d) < pivotValue(%d)", array[j], pivotValue));
swap(++i, j);
} else {
logger.info(format("Array[j](%d) >= pivotValue(%d)", array[j], pivotValue));
}
}
logger.info(format("%nMoving the pivot element right after values that are lower than itself"));
swap(++i, rightIndex);
return i;
}
private void swap(int i1, int i2) {
logger.info(format("Swapping array[%d](%d) and array[%d](%d)", i1, array[i1], i2, array[i2]));
int i1Value = array[i1];
array[i1] = array[i2];
array[i2] = i1Value;
}
}
It might look scarier than it is. We'll look at a simplified version at the end. The array is stored as an instance variable to avoid passing it constantly between different methods. This is probably not desirable in an implementation that you'd want to reuse with various arrays in a real program, but that isn't the case here. The logger is configured to print out additional information to help us figure out what is happening in the process.
As you can see, there's only one physical array. The subarrays mentioned above are purely logical. We use indexes to define data slices belonging to the left and right segments.
Taking apart
Sort method
The execution starts with the class initialization, and then we call the sort() method.
@Test
public void sortBaseArray() {
int[] input = {3, 7, 4, 8, 6}; // this array is different from the example in the introduction
int[] output = {3, 4, 6, 7, 8};
new QuickSort(input).sort();
assertThat(input).isEqualTo(output);
}
The parameterless sort() overloads the private sort(int leftIndex, int rightIndex) method to provide a simple interface for the caller, who might be clueless about starting values for leftIndex and rightIndex.
public void sort() {
sort(0, array.length - 1);
}
As this is the first time we're calling sort(int leftIndex, int rightIndex), we provide the lowest possible index (0) and the highest possible index, which is the array's length minus 1. For this particular array of 5 values, this translates to: sort(0, 4).
private void sort(int leftIndex, int rightIndex) {
logger.info(format("%n=====%n=> Sorting %s", Arrays.toString(Arrays.copyOfRange(array, leftIndex, rightIndex + 1))));
// leftIndex=0, rightIndex=4
if (leftIndex < rightIndex) {
logger.info(format("LeftIndex(%d) < rightIndex(%d), splitting into partitions", leftIndex, rightIndex));
int pivotIndex = partition(leftIndex, rightIndex);
// <...>
}
}
First, the program checks if leftIndex is less than rightIndex. This is the break condition that we'll discuss later. For now, the code inside this block will be executed because 0 < 4 is true. To split the array into two subarrays, the algorithm needs to find the pivot element. The partition(int leftIndex, int rightIndex) is responsible for that. It selects one element and rearranges the other elements around it, returning back the index of the pivot element.
Partition method
In this version, the pivot element is always the last element:
private int partition(int leftIndex, int rightIndex) {
int i = leftIndex - 1;
int pivotValue = array[rightIndex];
// <...>
}
The algorithm then iterates through all elements in the given segment (from leftIndex to rightIndex) and compares them to the pivot value.
private int partition(int leftIndex, int rightIndex) {
// <...>
for (int j = leftIndex; j < rightIndex; j++) {
if (array[j] < pivotValue) {
logger.info(format("Array[j](%d) < pivotValue(%d)", array[j], pivotValue));
swap(++i, j);
} else {
logger.info(format("Array[j](%d) >= pivotValue(%d)", array[j], pivotValue));
}
}
// <...>
}
The value of j increases with each iteration, pointing to the current element. However, the value of i points to the last element that is less than the pivot value. At the beginning of the partition(leftIndex, rightIndex) method, we declared that i = leftIndex - 1, i.e. i = -1. Essentially, at this point, there are no elements known to the program that are less than the pivot value. This will change soon.
Here's the first iteration of the for loop:
- Array =
[3, 7, 4, 8, 6],j=0,i=-1. array[j]with the value of3<pivotValuewith the value of6.- Move
array[j]to the index ofi + 1. - Move
array[i + 1]to the index ofarray[j].
Ultimately, it swaps array[0] with array[0]. This isn't much, but let's continue with the next iteration.
- Array =
[3, 7, 4, 8, 6],j=1,i=0. array[j]with the value of7>pivotValuewith the value of6.- Don't do anything.
Earlier, we discussed that values greater than the pivot element should go to the right of it. Why didn't we move 7 then? Because that'd increase the complexity of the algorithm, requiring another pointer to track where to put 7. This approach would be very close to the original idea of Tony Hoare. In this version, we will do something different.
Before that, we better finish with the remaining elements:
- Array =
[3, 7, 4, 8, 6],j=2,i=0. array[j]with the value of4<pivotValuewith the value of6.- Move
array[j]to the index ofi + 1. - Move
array[i + 1]to the index ofarray[j].
And finally:
- Array =
[3, 4, 7, 8, 6],j=3,i=1. array[j]with the value of8<pivotValuewith the value of6.- Don't do anything.
Now all elements are reordered according to their relationship to 6: [3, 4, 7, 8, 6]. This is where the i value comes in handy to finalize the partitioning:
private int partition(int leftIndex, int rightIndex) {
// <...>
logger.info(format("%nMoving the pivot element right after values that are lower than itself"));
swap(++i, rightIndex);
return i;
}
Instead of shifting 8 and 7 to the right of the pivot element, the program moves the pivot element itself. Since the i variable points to the rightmost lowest value of 4, a swap between i + 1 and rightIndex does exactly that: it transforms the array from [3, 4, 7, 8, 6] to [3, 4, 6, 8, 7].
Method call: partition([3, 7, 4, 8, 6], 0, 4)
Select the pivot element:
[3, 7, 4, 8, 6]
|- the pivot element
Sort elements around it:
[3, 4, 6, 8, 7]
|- the pivot element is sorted
return 2 - the index of the pivot point
Back to sort method
private void sort(int leftIndex, int rightIndex) {
logger.info(format("%n=====%n=> Sorting %s", Arrays.toString(Arrays.copyOfRange(array, leftIndex, rightIndex + 1))));
if (leftIndex < rightIndex) {
logger.info(format("LeftIndex(%d) < rightIndex(%d), splitting into partitions", leftIndex, rightIndex));
int pivotIndex = partition(leftIndex, rightIndex);
sort(leftIndex, pivotIndex - 1);
sort(pivotIndex + 1, rightIndex);
} else {
logger.info(format("LeftIndex(%d) >= rightIndex(%d)", leftIndex, rightIndex));
}
}
Now that the pivotIndex is calculated, subarrays can be defined and sorted separately:
int pivotIndex = partition(leftIndex, rightIndex);
sort(leftIndex, pivotIndex - 1);
sort(pivotIndex + 1, rightIndex);
One subarray consists of elements [3, 4] and the other consists of elements [8, 7]. In both cases, the pivot element is excluded from the range (thus pivotIndex - 1/pivotIndex + 1). The entire process is repeated for each segment and their subarrays (if any). Let's examine the output produced by the logger for the elements [3, 4]:
=====
=> Sorting [3, 4]
LeftIndex(0) < rightIndex(1), splitting into partitions
Sorting partition from leftIndex(0) to rightIndex(1)
Taking the rightmost value (array[1]=4) as the pivot value
Array[j](3) < pivotValue(4)
Swapping array[0](3) and array[0](3)
Moving the pivot element right after values that are lower than itself
Swapping array[1](4) and array[1](4)
=====
=> Sorting [3]
LeftIndex(0) >= rightIndex(0)
=====
=> Sorting []
LeftIndex(2) >= rightIndex(1)
It turned out that this segment was already sorted, but the algorithm didn't know that in advance. Then, these two elements are split into two more subarrays with ranges of 0 to 0 and 2 to 1. This is where the break condition stops the execution, as leftIndex is no longer less than rightIndex.
private void sort(int leftIndex, int rightIndex) {
logger.info(format("%n=====%n=> Sorting %s", Arrays.toString(Arrays.copyOfRange(array, leftIndex, rightIndex + 1))));
if (leftIndex < rightIndex) {
// <...>
}
}
The same happens with the second call to the sort(int, int) method:
=====
=> Sorting [8, 7]
LeftIndex(3) < rightIndex(4), splitting into partitions
Sorting partition from leftIndex(3) to rightIndex(4)
Taking the rightmost value (array[4]=7) as the pivot value
Array[j](8) >= pivotValue(7)
Moving the pivot element right after values that are lower than itself
Swapping array[3](8) and array[4](7)
=====
=> Sorting []
LeftIndex(3) >= rightIndex(2)
=====
=> Sorting [8]
LeftIndex(4) >= rightIndex(4)
Only this time, the program actually swaps 8 and 7, completing the task.
Clean version
Here's a clean implementation without auxiliary methods and the logger. Without them, the code is much shorter and simpler:
public class QuickSortSimplified {
public static void sort(int[] array, int leftIndex, int rightIndex) {
if (leftIndex < rightIndex) {
int pivotIndex = partition(array, leftIndex, rightIndex);
sort(array, leftIndex, pivotIndex - 1);
sort(array, pivotIndex + 1, rightIndex);
}
}
private static int partition(int[] array, int leftIndex, int rightIndex) {
int i = leftIndex - 1;
int pivotValue = array[rightIndex];
for (int j = leftIndex; j < rightIndex; j++) {
if (array[j] < pivotValue) {
swap(array, ++i, j);
}
}
swap(array, ++i, rightIndex);
return i;
}
private static void swap(int[] array, int i1, int i2) {
int i1Value = array[i1];
array[i1] = array[i2];
array[i2] = i1Value;
}
}
A few tests:
public class QuickSortSimplifiedTest {
@Test
public void sortBaseArray() {
int[] input = {3, 7, 4, 8, 6};
int[] output = {3, 4, 6, 7, 8};
QuickSortSimplified.sort(input, 0, input.length - 1);
assertThat(input).isEqualTo(output);
}
@Test
public void sortSortedArray() {
int[] input = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int[] output = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
QuickSortSimplified.sort(input, 0, input.length - 1);
assertThat(input).isEqualTo(output);
}
@Test
public void sortReversedArray() {
int[] input = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
int[] output = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
QuickSortSimplified.sort(input, 0, input.length - 1);
assertThat(input).isEqualTo(output);
}
@Test
public void sortMixedArray() {
int[] input = {9, 1, 7, 6, 0, 4, 2, 3, 8, 5};
int[] output = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
QuickSortSimplified.sort(input, 0, input.length - 1);
assertThat(input).isEqualTo(output);
}
@Test
public void sortMixedArrayEqualValues() {
int[] input = {9, 1, 7, 5, 0, 4, 2, 3, 1, 5};
int[] output = {0, 1, 1, 2, 3, 4, 5, 5, 7, 9};
QuickSortSimplified.sort(input, 0, input.length - 1);
assertThat(input).isEqualTo(output);
}
}
GeeksforGeeks offers implementations for C++, Python, and JavaScript.
Conclusion
I enjoyed diving into quicksort. Not only do I understand it much better now, but I also gained a different perspective thanks to additional information I found on Wikipedia and some other resources.
Turns out, quicksort is not just a simple algorithm that only computer science teachers and students use. It's considered to be quite effective, thanks to its good average run time. Different versions address various weak spots, leaving room for improvement based on a specific use-case.
Moreover, I learned that the quicksort algorithm was developed in 1959 by Tony Hoare while he was a visiting student at Moscow State University. At that time, he was working on a machine translation project. I remember the quality of machine translation 15 years ago, it was much worse than it is today. I can't imagine how it was in the '50s! It never fails to amaze me what people were able to accomplish with the technologies of that time. To this day, we're using the results of their labor.