# 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:

1. Partition the list around the pivot number.
2. Repeat this with the numbers smaller than the pivot number.
3. 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:

1. 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:

1. 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.

# How to Implement Insertion Sort

Insertion Sort goes from the second through the last number in a list, performing these steps with each number:

• Compare with the previous number
• If it’s less than the previous number, swap it with that number
• If swapped, then repeat this with the number before that…
• …and so on, until we find a number that’s not bigger than it, or we reach the beginning of the list.

Pretty simple, right?  Okay, but how do we make a computer actually do this?  Just follow those steps!

A program in the language called C++ doing this might look like:

```int main() {
int the_list[] = {3, 7, 8, 5, 2, 1, 9, 5, 4};
int size_of_the_list = 9;

for (int current_index = 1;
current_index < size_of_the_list;
++current_index) {
// Put the_list[current_index] into its rightful place
// among all preceding numbers.
}

return 0;
}```

If you’re not familiar with C++, the “int main()” just indicates where the program starts and you can basically ignore it, just like when you read, “Once upon a time,” in a story.

Similarly, “return 0” just means the program shall end successfully when that line of code is executed, so you can basically ignore it, just like “The End” in a story.

You can probably tell that the first “real” line of code is just listing the 9 numbers we want to sort, and the second line is just specifying how many numbers are in that list to be sorted (9).

Then, there is this thing called a “for loop,” which:

• executes the first command in it (int current_index = 1) once,
• checks the “loop condition” (whether current_index is less than size_of_the_list),
• and if that condition is true, then runs whatever code is between the braces {},
• and then runs the “loop increment” (++current_index, which means the same as current_index = current_index + 1, or in plain English, “increase current_index by one”).

Then, the for loop again checks the loop condition and if it’s true, it again runs the code inside the braces, and then does the loop increment again, and then checks the loop condition again, and if it’s true, runs the code inside the braces, does the loop increment again, etc. This just keeps repeating until the loop condition ends up being false.

But this isn’t a complete program yet: notice that inside the braces of the loop, all we have is a couple lines in plain English starting with two slashes.  This is called a “comment” and is not “really” part of the code–it’s just an aid to someone reading the code to describe what needs to happen in that part of the code.

Okay, so how do we write the code to implement what the comment says?  How do we take a number in a list and keep comparing and swapping it with all numbers that come before it that are bigger than it, until we reach a number that isn’t bigger than it (or, we reach the beginning of the list)?  Well, that sounds like something we keep repeating… which means, we need another loop!

What should this new loop do?  Well,

• if we set j to current_index,
• the loop should take the number the_list[j] and compare it with the_list[j-1],
• and if the latter number is bigger, then swap these two numbers.
• If we did end up swapping these two numbers, then the number of interest is now at the_list[j-1].
• So in that case, let’s set j equal to j-1, so now the number of interest is at the_list[j].
• Then we should continue up the list, checking if the_list[j] is smaller than the number before it, the_list[j-1], and swapping if so, and so on, …
• until either j is 0, meaning we’re at the beginning of the list, or the_list[j-1] is not bigger than the_list[j].

So now we’ve figured out:

• where we should start this for loop (int j = current_index),
• what we should check before we run the loop each time (j > 0 and the_list[j] < the_list[j-1]),
• and what we should do inside the loop (swap the_list[j] and the_list[j-1]).
• We also know how to update j after each time the loop runs: j = j – 1, or in C++ shorthand, –j.

So let’s plug that into our code where that comment was:

```int main() {
int the_list[] = {3, 7, 8, 5, 2, 1, 9, 5, 4};
int size_of_the_list = 9;

for (int current_index = 1;
current_index < size_of_the_list;
++current_index) {
// Put the_list[current_index] into its rightful place
// among all preceding numbers.
for (int j = current_index;
j > 0 && the_list[j] < the_list[j-1];
--j) {
// Swap the_list[j] and the_list[j-1].
}
}

return 0;
}

```

Okay, now all we have left is to figure out how to swap two numbers!  That’s simple: just create a third number as a placeholder, like this:

```int main() {
int the_list[] = {3, 7, 8, 5, 2, 1, 9, 5, 4};
int size_of_the_list = 9;

for (int current_index = 1;
current_index < size_of_the_list;
++current_index) {
// Put the_list[current_index] into its rightful place
// among all preceding numbers.
for (int j = current_index;
j > 0 && the_list[j] < the_list[j-1];
--j) {
// Swap the_list[j] and the_list[j-1].
int placeholder = the_list[j];
the_list[j] = the_list[j-1];
the_list[j-1] = placeholder;
}
}

return 0;
}

```

Let’s also add some lines of code to print the sorted list to the computer screen, so we can see that this program actually does what we want!

```#include <iostream>

int main() {
int the_list[] = {3, 7, 8, 5, 2, 1, 9, 5, 4};
int size_of_the_list = 9;

for (int current_index = 1;
current_index < size_of_the_list;
++current_index) {
// Put the_list[current_index] into its rightful place
// among all preceding numbers.
for (int j = current_index;
j > 0 && the_list[j] < the_list[j-1];
--j) {
// Swap the_list[j] and the_list[j-1].
int placeholder = the_list[j];
the_list[j] = the_list[j-1];
the_list[j-1] = placeholder;
}
}

// Print the sorted list to the computer screen.
for (int i = 0; i < size_of_the_list; ++i) {
std::cout << the_list[i] << “ “;
}
std::cout << std::endl;

return 0;
}```

And voila, we have a complete computer program that implements the Insertion Sort algorithm!  Read more on Wikipedia about how this implementation can be improved.

# An Assignment Is One Kind of Instruction

An assignment, like we just saw, is one kind of instruction.

# Ingredients of a Program Are Variables. What Are Instructions?

So, you’ve learned what the ingredients of a program are: variables.  But what do the instructions of a program look like?