CS Comics

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.