How to Implement Quicksort
Let’s take a higher-level look at how the Quicksort algorithm actually worked. First, we partitioned the list by picking the first number in the list to be the pivot number, and then moving all the numbers smaller than the pivot number to its left, while moving all bigger numbers to its right. Then, we repeated this partitioning process with only those smaller numbers, and then only the bigger numbers. So, that process looks something like this:
- Partition the list around the pivot number.
- Repeat this with the numbers smaller than the pivot number.
- Repeat this with the numbers bigger than the pivot number.
Now, let’s figure out how to write code to make a computer do each of these steps for us.
The first step above, the partitioning process, works as shown here: pick the pivot number to be the first one in the list, place the left and right index markers at the pivot and past the end of the list, respectively, and then do the following over and over:
- Partition the list around the pivot number.
- (a) March the left index marker forward until it reaches a number bigger than or equal to the pivot number. If it’s about to run off the right end of the list, stop everything and swap the number at the right index with the pivot number.
- (b) March the right index marker backward until it reaches a number smaller than or equal to the pivot number. If it’s about to run off the left end of the list, stop everything and swap the number at the right index with the pivot number.
- (c) If the right index marker has reached or passed the left index marker, stop everything and just swap the number at the right index with the pivot number.
- (d) Otherwise, swap the left and right numbers and repeat the steps above.
Okay, so we can start writing our program to perform these steps. First, we know it should do something like this:
int main() {
int the_list[] = {3, 7, 8, 5, 2, 1, 9, 5, 4};
// Sort the list.
return 0;
}
And then, the “Sort the list” part should be doing something like:
// 1. Partition the list around the pivot (first) number. // 2. Sort the numbers to the left of the pivot number. // 3. Sort the numbers to the right of the pivot number.
And that first step, partitioning, would involve the four steps above, 1a through 1d. Let’s dig deeper into those steps, breaking them down and writing code for them, since those steps really are the bulk of what needs to get done.
First, 1a says we need to march the left index marker forward until it reaches a number bigger than or equal to the pivot number. Well, from the comic, we know that the left index marker, “L”, starts at the first number (the pivot number) and then marches forward. Each time we march the left index marker forward by one spot, we check if it is now at a number bigger than or equal the pivot number. If not, we march it forward again, check again if it’s at a number bigger than or equal to the pivot, etc., stopping when we find such a number.
So, these steps should follow a strategy like:
int pivot = 0; // Set pivot to index first number.
int left = 0; // Start left index marker at first number.
do {
// March the left index marker forward (to the right) by
// one spot in the list.
} while (/* something */);
Note here that we used another kind of comment, /* … */, that exists within a single line of code. The “something” should say that “the left index marker is on a number that is smaller the pivot number.” In code, “left index marker” is the variable “left” and the number it’s on is “the_list[left]”. The pivot number is the number at index “pivot” in “the_list”, which would be “the_list[pivot]”. To say the former number is smaller than the latter number, we would write in code, “the_list[left] < the_list[pivot]”.
Marching the left index marker forward (to the right) by one spot, as the comment above says, is easy to write in code: that means we just take “left” and add one to it, and store the result back in “left”. One way to write that in code is “left = left + 1”, though in the C++ programming language, there is a shorthand for that, “++left”.
So, replacing the code in the comments above with what we explained in the last two paragraphs gives us:
int pivot = 0;
int left = 0;
do {
++left;
} while (the_list[left] < the_list[pivot]);
We do the exact opposite thing for the right index marker:
- Start it just beyond the index of the last number in the list
- March it backward…
- …as long as it’s at a number bigger than the pivot number.
The code for the first statement could create a variable called “right” to represent the right index marker and set it equal to one more than the index of the last number in the list. There are nine numbers in the list, from index 0 through index 8, so we can define this variable to 8 + 1 = 9 in a single line of code as “int right = 9;”.
The code for the second statement would be the opposite of what we did for “left”: set right equal to right – 1, which in C++ can be done in a single shorthand command: “–right;”.
The third statement indicates a condition that’s the opposite of the left index marker’s condition: that the right index marker is at a number bigger than the pivot number. This can be written as “the_list[right] > the_list[pivot]”.
Adding these statements to the code above, we have:
int pivot = 0;
int left = 0;
int right = 9; // Put right marker after last number.
do {
++left;
} while (the_list[left] < the_list[pivot]);
do {
--right;
} while (the_list[right] > the_list[pivot]);
Okay, so we’ve got parts of steps 1a and 1b done now, but there’s still some stuff missing. For example, our instructions in step 1d said to “repeat the steps above” over and over, at least as long as the right index marker is still to the right of the left index marker as we check in step 1c. To keep repeating the steps above, we can wrap them in another loop like this:
int pivot = 0;
int left = 0;
int right = 9;
while (true) {
do {
++left;
} while (the_list[left] < the_list[pivot]);
do {
--right;
} while (the_list[right] > the_list[pivot]);
}
And then, to check whether the right index marker has reached or moved left of the left index marker, and then break out of this loop and swap the right and pivot numbers, we want to add something like:
int pivot = 0;
int left = 0;
int right = 9;
while (true) {
do {
++left;
} while (the_list[left] < the_list[pivot]);
do {
--right;
} while (the_list[right] > the_list[pivot]);
if (/* right has reached or passed left */) {
break;
}
}
// Swap the_list[right] and the_list[pivot].
The first comment, checking that the right index marker has reached or moved left of the left index marker, is easy to fill in: that’s just checking that right is equal to or less than left, i.e., “right <= left”. The second comment, for swapping two numbers, is also easy to do, with the help of a third number used as a placeholder:
int pivot = 0;
int left = 0;
int right = 9;
while (true) {
do {
++left;
} while (the_list[left] < the_list[pivot]);
do {
--right;
} while (the_list[right] > the_list[pivot]);
if (right <= left) {
break;
}
}
// Swap the_list[right] and the_list[pivot].
int placeholder = the_list[right];
the_list[right] = the_list[pivot];
the_list[pivot] = placeholder;
Okay, so we’ve now done some of 1a and 1b, all of 1c, and just the “repeat the steps above” part of 1d. What remains to be implemented in our code here? The things we haven’t implemented yet are listed in boldface below:
- Partition the list around the pivot number.
- (a) March the left index marker forward until it reaches a number bigger than or equal to the pivot number. If it’s about to run off the right end of the list, stop everything and swap the number at the right index with the pivot number.
- (b) March the right index marker backward until it reaches a number smaller than or equal to the pivot number. If it’s about to run off the left end of the list, stop everything and swap the number at the right index with the pivot number.
- (c) If the right index marker has reached or passed the left index marker, stop everything and just swap the number at the right index with the pivot number.
- (d) Otherwise, swap the left and right numbers and repeat the steps above.
Okay, so notice that the phrase, “stop everything and swap the number at the right index with the pivot number” appears in 1a, 1b, AND in 1c. So, we’ve already implemented this for 1c, using the “break” command and then leaving the loop, which results in executing the lines of code for swapping the_list[right] and the_list[pivot]. So, for 1a, we just need to add another “break” command when that condition, that the left index marker has reached the right end of the list, occurs. That’s easy enough to do as follows:
int pivot = 0;
int left = 0;
int right = 9;
while (true) {
do {
if (left == 8) {
break;
}
++left;
} while (the_list[left] < the_list[pivot]);
do {
--right;
} while (the_list[right] > the_list[pivot]);
if (right <= left) {
break;
}
}
// Swap the_list[right] and the_list[pivot].
int placeholder = the_list[right];
the_list[right] = the_list[pivot];
the_list[pivot] = placeholder;
And we can do the same thing for the analogous condition in 1b:
int pivot = 0;
int left = 0;
int right = 9;
while (true) {
do {
if (left == 8) {
break;
}
++left;
} while (the_list[left] < the_list[pivot]);
do {
if (right == 0) {
break;
}
--right;
} while (the_list[right] > the_list[pivot]);
if (right <= left) {
break;
}
}
// Swap the_list[right] and the_list[pivot].
int placeholder = the_list[right];
the_list[right] = the_list[pivot];
the_list[pivot] = placeholder;
Okay, now all we have left to add for partitioning is the boldface phrase in 1d, to swap the left and right numbers if the right and left index markers haven’t yet crossed paths:
int pivot = 0;
int left = 0;
int right = 9;
while (true) {
do {
if (left == 8) {
break;
}
++left;
} while (the_list[left] < the_list[pivot]);
do {
if (right == 0) {
break;
}
--right;
} while (the_list[right] > the_list[pivot]);
if (right <= left) {
break;
}
// Swap the_list[left] and the_list[right].
int placeholder = the_list[left];
the_list[left] = the_list[right];
the_list[right] = placeholder;
}
// Swap the_list[right] and the_list[pivot].
int placeholder = the_list[right];
the_list[right] = the_list[pivot];
the_list[pivot] = placeholder;
Okay, so we have written all the code for our partitioning! Are we done? No, the code above still doesn’t quite look like a full program, does it? There’s no “int main()” or any of that stuff, and we haven’t added the code yet for separately sorting the numbers smaller and bigger than the pivot either.
Going back to the beginning, remember how we wanted our program to look like this…
int main() {
int the_list[] = {3, 7, 8, 5, 2, 1, 9, 5, 4};
// Sort the list.
return 0;
}
…with the “Sort the list” part doing:
// 1. Partition the list around the pivot (first) number. // 2. Sort the numbers to the left of the pivot number. // 3. Sort the numbers to the right of the pivot number.
Well, it seems like each of these comments is describing another little “program within a program.” It’s like we want to repeat some things, like partitioning, first with our original list and then with smaller sub-lists to the left and right of the pivot, which involves further partitioning those smaller lists and then sorting their left and right sub-lists, etc., until everything gets sorted.
To be able to run “little programs inside a program,” we make use of something called a function. We won’t go into great detail on this topic here, but we will show just enough to be able to write a computer program that implements the Quicksort algorithm. First, we want a mini-program, a function, that can fill in the comment where we say “Sort the list.” That could look something like this:
int main() {
int the_list[] = {3, 7, 8, 5, 2, 1, 9, 5, 4};
quicksort(the_list);
return 0;
}
The “quicksort” function could then do the remaining three comments above, somehow:
void quicksort(int the_list[]) {
// 1. Partition the list around the pivot number.
// 2. Sort the numbers to the left of the pivot number.
// 3. Sort the numbers to the right of the pivot number.
}
We wrote the code for step 1 above, but how do we handle steps 2 and 3? It seems like we want to call this exact same function, “quicksort”, again, but this time on only a portion of the list for step 2 and for another portion of the list for step 3. So, we’ll need a way to specify not only that we want to sort the list, but that we want to sort a certain range of numbers within the list. To do that, let’s add a couple more parameters, or values, representing the first and last index of the numbers that we want sorted by this function. The first time this function gets called in our program above, we want the whole list to get partitioned and sorted, so we should pass in the first (0) and last (8) index of the entire list at that time:
int main() {
int the_list[] = {3, 7, 8, 5, 2, 1, 9, 5, 4};
quicksort(the_list, 0, 8);
return 0;
}
void quicksort(int the_list[], int low, int high) {
// 1. Partition the list around the pivot number.
// 2. Sort the numbers to the left of the pivot number.
// 3. Sort the numbers to the right of the pivot number.
}
Okay, and then how do we fill in the code for step 2? Well, the numbers to the left of the pivot number range from index “low” to index “pivot number’s index minus 1”, while the numbers to the right of the pivot number range from index “pivot number plus 1” to “high”. So, if step 1 somehow gave us the pivot number’s index, then we could implement step 2 like this:
void quicksort(int the_list[], int low, int high) {
// 1. Partition the list around the pivot number.
int pivot = ???
// 2. Sort the numbers to the left of the pivot number.
quicksort(the_list, low, pivot - 1);
// 3. Sort the numbers to the right of the pivot number.
}
And then step 3 could easily be done in a similar way:
void quicksort(int the_list[], int low, int high) {
// 1. Partition the list around the pivot number.
int pivot = ???
// 2. Sort the numbers to the left of the pivot number.
quicksort(the_list, low, pivot - 1);
// 3. Sort the numbers to the right of the pivot number.
quicksort(the_list, pivot + 1, high);
}
It may seem odd, but we are done with steps 2 and 3 here; and yes, it may seem odd that this function, quicksort, is calling itself. This is called recursion: where a function calls itself on a smaller version of the same problem that it originally set out to solve. Don’t worry if that doesn’t make total sense to you. Perhaps the most important thing when implementing recursion is to make sure that it ends! Because when a function calls itself, then it calls itself again on a smaller version of the same problem, which causes it to call itself again on an even smaller version of the problem, etc., … but you have to make it stop when the problem becomes so tiny there’s nothing to do! In our case, when the range of numbers we want to sort becomes one number or less, then of course we don’t want to do any more recursion, since by definition, zero or one number is already sorted as is – there is no work to do to sort it!
To handle that, we add a little code snippet to the beginning of the quicksort function to stop doing further recursion when this situation occurs:
void quicksort(int the_list[], int low, int high) {
// Catch the recursion edge cases where our range
// [low, high] contains one number or less, and so there
// is nothing to sort.
if (high <= low) {
return;
}
// 1. Partition the list around the pivot number.
int pivot = ???
// 2. Sort the numbers to the left of the pivot number.
quicksort(the_list, low, pivot - 1);
// 3. Sort the numbers to the right of the pivot number.
quicksort(the_list, pivot + 1, high);
}
Now, all we have left to do in terms of writing code is filling in the code for step 1 here. We already wrote the code for this above, so we just need to weave that code into here somehow. A nice way to do that is to write another function that encloses all that partitioning code we just wrote:
void partition(int the_list[]) {
int pivot = 0;
int left = 0;
int right = 9;
while (true) {
do {
if (left == 8) {
break;
}
++left;
} while (the_list[left] < the_list[pivot]);
do {
if (right == 0) {
break;
}
--right;
} while (the_list[right] > the_list[pivot]);
if (right <= left) {
break;
}
// Swap the_list[left] and the_list[right].
int placeholder = the_list[left];
the_list[left] = the_list[right];
the_list[right] = placeholder;
}
// Swap the_list[right] and the_list[pivot].
int placeholder = the_list[right];
the_list[right] = the_list[pivot];
the_list[pivot] = placeholder;
}
Okay, but we need this function to give us the pivot number’s index in the list. To do that, we add a line at the end: “return right;” to give us the location to which we moved the pivot number, and change the “void” at the beginning of this function to “int”:
int partition(int the_list[]) {
int pivot = 0;
int left = 0;
int right = 9;
while (true) {
do {
if (left == 8) {
break;
}
++left;
} while (the_list[left] < the_list[pivot]);
do {
if (right == 0) {
break;
}
--right;
} while (the_list[right] > the_list[pivot]);
if (right <= left) {
break;
}
// Swap the_list[left] and the_list[right].
int placeholder = the_list[left];
the_list[left] = the_list[right];
the_list[right] = placeholder;
}
// Swap the_list[right] and the_list[pivot].
int placeholder = the_list[right];
the_list[right] = the_list[pivot];
the_list[pivot] = placeholder;
return right;
}
But there’s one more issue; we’re going to want to be able to run this function for different ranges of values, like partitioning the entire list, or partitioning just the values left of the pivot value, etc. So, we’ll add parameters (“low” and “high”) again to this function like we did for the quicksort function above to specify that range, and also change the “0”s to “low” and “8”s to “high” and therefore “9”s to “high + 1”:
int partition(int the_list[], int low, int high) {
int pivot = low;
int left = low;
int right = high + 1;
while (true) {
do {
if (left == high) {
break;
}
++left;
} while (the_list[left] < the_list[pivot]);
do {
if (right == low) {
break;
}
--right;
} while (the_list[right] > the_list[pivot]);
if (right <= left) {
break;
}
// Swap the_list[left] and the_list[right].
int placeholder = the_list[left];
the_list[left] = the_list[right];
the_list[right] = placeholder;
}
// Swap the_list[right] and the_list[pivot].
int placeholder = the_list[right];
the_list[right] = the_list[pivot];
the_list[pivot] = placeholder;
return right;
}
Now, we can complete our quicksort function:
void quicksort(int the_list[], int low, int high) {
// Catch the recursion edge cases where our range
// [low, high] contains one number or less, and so there
// is nothing to sort.
if (high <= low) {
return;
}
// 1. Partition the list around the pivot number.
int pivot = partition(the_list, low, high);
// 2. Sort the numbers to the left of the pivot number.
quicksort(the_list, low, pivot - 1);
// 3. Sort the numbers to the right of the pivot number.
quicksort(the_list, pivot + 1, high);
}
Note what we did here. When we changed the “void” to “int” in the partition function, we were basically saying that that whole function calculates this value, the index of the location where the pivot number ends up in the list, and “return” it, meaning that we kind of toss it back to where the function was called in the first place. So, the “int pivot” variable above now stores the value that was returned from the partition function, so it can be used in the code for steps 2 and 3 below it.
And so, we have arrived at our complete program that implements the Quicksort algorithm on this list of numbers! Note in the program below that we’ve also added some code to print out the numbers in the sorted list at the end.
#include <iostream>
int partition(int the_list[], int low, int high) {
int pivot = low;
int left = low;
int right = high + 1;
while (true) {
do {
if (left == high) {
break;
}
++left;
} while (the_list[left] < the_list[pivot]);
do {
if (right == low) {
break;
}
--right;
} while (the_list[right] > the_list[pivot]);
if (right <= left) {
break;
}
// Swap the_list[left] and the_list[right].
int placeholder = the_list[left];
the_list[left] = the_list[right];
the_list[right] = placeholder;
}
// Swap the_list[right] and the_list[pivot].
int placeholder = the_list[right];
the_list[right] = the_list[pivot];
the_list[pivot] = placeholder;
return right;
}
void quicksort(int the_list[], int low, int high) {
// Catch the recursion edge cases where our range
// [low, high] contains one number or less, and so there
// is nothing to sort.
if (high <= low) {
return;
}
// 1. Partition the list around the pivot number.
int pivot = partition(the_list, low, high);
// 2. Sort the numbers to the left of the pivot number.
quicksort(the_list, low, pivot - 1);
// 3. Sort the numbers to the right of the pivot number.
quicksort(the_list, pivot + 1, high);
}
int main() {
int the_list[] = {3, 7, 8, 5, 2, 1, 9, 5, 4};
quicksort(the_list, 0, 8);
std::cout << "Sorted list:";
for (int i = 0; i < 9; ++i) {
std::cout << " " << the_list[i];
}
std::cout << std::endl;
return 0;
}
Many improvements can be made to this program to handle things like choosing better pivot numbers. See this website and an example implementation as a Java program linked from that website for more information. The Wikipedia page on Quicksort also has more details and variations on the algorithm.
Discussion ¬