Insertion Sort In C#

Posted on Posted in Algorithms

What is it?

Think of a deck of cards that’s been shuffled and is turned face up. Now let’s say you want to put all the hearts on top, starting with the two of hearts, then the three of hearts, etc… So that if you looked at the top face-up card you’d see the two of hearts, then the three, then the four, etc…

Well insertion sort says that you should go through the entire deck and find the two of hearts, then put it on top. Then go through the entire deck and find the three of  hearts and put it underneath the two of hearts. Rinse and repeat this and that’s how the insertion sort algorithm works.

Note: The below example can be found on github.

How It Works

An insertion sort algorithm works by moving through a list, from beginning to end, and placing each item it encounters wherever it fits in the portion it’s already sorted. That might still sound a little complicated, so let’s simplify it.

So let’s start with what we know. The insertion sort works by going through the list and comparing each item. For the sake of argument we’ll start with an array that holds random values.

// Create an array with a random length
int[] intArrRandom = new int[rand.Next(0, 100)];

// For each place in the array
for (int i = 0; i < intArrRandom.Count(); i++)

{

 // Put a random number in it
 intArrRandom[i] = rand.Next(0, 100);

}

Now we’ve got our input and we know it’s totally random, so let’s sort this thing.

Well to start we know we need to go through the array, so how do we go through an array? Well, I don’t know about you, but a for loop sounds pretty good to me.

// For each place in the array
for (int intCurrentLocation = 0; intCurrentLocation < intArrRandom.Count(); intCurrentLocation++)
{
}

So this loop will let us go through the array one at a time. The insertion sort wants to start at the beginning of an input (array in this case) and sort from there until the end. So we’ve got to go one at a time, finding a value’s place in the array of items (from the beginning to wherever the for loop is) that have already been sorted. Since we’ve got to go one at a time, let’s get the value in the array that matches wherever the for loop is.

// For each place in the array
for (int intCurrentLocation = 0; intCurrentLocation < intArrRandom.Count(); intCurrentLocation++)
{
 // Get the value of the current location
 int intCurrentValue = intArrRandom[intCurrentLocation];
}

Now we’ve got to ‘sort and compare’ our current value, to the other sorted values until we find our current value’s home. Whenever I hear ‘compare’, and we’re talking about lists/arrays, I usually find that we’ve got a nested loop on our hands (for the math kids out there, this is the code that just screams O(n)2). But before we throw this next loop out there, let’s think a minute. We don’t need to ‘compare’ a value to every other value in the array, we just need to ‘compare’ it to every value that’s already been sorted.

Note: This loop could go from the beginning to our current location, or from our current location back to the beginning. If you know the texture of your data one might (often) be better than the other, but here we’ll just work from our current location backwards.

Here we’re going to work from our current location back to the beginning of the array. You could do this with any sort of loop, but personally I prefer to loop through subsets with a while loop. Moreover, we’re looking to compare values, true/false tests like this can easily be part of a while statement so that makes it an even better choice for our inner iterator.

Since we’ll be going backwards (and the while loop doesn’t natively track location like a for loop) we’re going to have to keep track of where our inner loop is at. We also don’t want to go past (i.e. zero) the beginning of our loop.

So let’s start by getting the place right before our current location. This will start us off at the very end of the sorted part of our array.

 // Get the prior location
 int intPriorLocation = intCurrentLocation - 1;

In our while loop, we can use this value to check that we haven’t gone past the beginning of the array and to ‘compare’ our values.

// For each place in the array
for (int intCurrentLocation = 0; intCurrentLocation < intArrRandom.Count(); intCurrentLocation++)
{
 
 // Get the value of the current location
 int intCurrentValue = intArrRandom[intCurrentLocation];
 
 // If the prior location is the first or greater positon
 // And the prior location's value is greater than the current value
 while (intPriorLocation >= 0 && intArrRandom[intPriorLocation] > intCurrentValue)

 {

 }

}

So our inner loop is just going back to the beginning of the array, trying to find where there’s a value that’s greater than our current value. Why greater? Well the point of this is that we’re moving back down our list, which means we’re going from our biggest values to our smallest values. So since we’re starting with our biggest values, we want to blow past everything bigger than our current value until we find where our current value should live.

Now, array’s are kind of annoying because you can’t actually ‘insert’ values into them and you can’t (easily) change their size. Now we’ve got our current value, so we’re just going to page through the other values we pass and move each one of them up one. This way we don’t change the size of the array and we can easily just plop our current value into wherever we find his home to be.

// For each place in the array
for (int intCurrentLocation = 0; intCurrentLocation < intArrRandom.Count(); intCurrentLocation++)
{
 
 // Get the value of the current location
 int intCurrentValue = intArrRandom[intCurrentLocation];
 
 // If the prior location is the first or greater positon
 // And the prior location's value is greater than the current value
 while (intPriorLocation >= 0 && intArrRandom[intPriorLocation] > intCurrentValue)

 {

  // Then we need to move the prior value up one, since it's greater than our current value
  intArrRandom[intPriorLocation + 1] = intArrRandom[intPriorLocation];

  // And move back down the list, looking for a value smaller than our current value
  intPriorLocation = intPriorLocation - 1;

 }

}

So this inner loop is going to go until it either hits the beginning of the array, or it finds a prior value who is NOT bigger than our current value (i.e. the prior value is smaller). Either way, we’ve found our current value’s happy place. It fits right in between two values (or at the start of the array). Now we just have to move him in.

// For each place in the array
for (int intCurrentLocation = 0; intCurrentLocation < intArrRandom.Count(); intCurrentLocation++)
{
 
 // Get the value of the current location
 int intCurrentValue = intArrRandom[intCurrentLocation];
 
 // If the prior location is the first or greater positon
 // And the prior location's value is greater than the current value
 while (intPriorLocation >= 0 && intArrRandom[intPriorLocation] > intCurrentValue)

 {

  // Then we need to move the prior value up one, since it's greater than our current value
  intArrRandom[intPriorLocation + 1] = intArrRandom[intPriorLocation];

  // And move back down the list, looking for a value smaller than our current value
  intPriorLocation = intPriorLocation - 1;

 }

 // Once we've either come to the end of the list or found the current values proper location
 intArrRandom[intPriorLocation + 1] = intCurrentValue; 

}

Algorithm Category: Decrease & Conquer

The insertion sort is a type of algorithm that tries to order something by finding the correct place for one item, then the next, and the next, etc… So each time it’s decreasing the problem by one to conquer it.

Best Case Scenario:

So, inherently, it has to loop through the entire input (e.g. array or list) at least once (O(n)). However, this only happens if the input is already (ascending) ordered.

Worst Case Scenario:

The worst case scenario is if the input is in exactly opposite (descending) order. This means it will have to go through the entire list twice (O(n)2) to place each item (because the last item will need to be moved to the front, the second to last item to the second in line, etc…).

Think about it

How could we make an insertion sort that puts the data in descending (biggest to smallest), rather than ascending (smallest to biggest), order?

Note: This example can be found on github.

Leave a Reply