Sorting (Part 3.0): Insertion Sort

Note: a bug was found in the Insertion Sort implementations. The bug was corrected in each language. Please refer to the pastebin links for the most up-to-date versions of the sample code. Any screenshots may be behind. More about the bug can be found here.

Hello World! Today I'll be talking about Insertion Sort.

What Is Insertion Sort?

Insertion Sort is a particular O(n^2), O(n), sorting algorithm that goes through an array and, if an element A is smaller than the element to its left, shifts all the elements greater than A to the right one space to insert A into the proper space.

It's worse case time complexity, O(n^2), happens when the inputted array is in reverse order, since all the elements will have to be shifted and read.

The best case, O(n), takes place when the array to sort is already sorted.

Let's Ruby It

Here is the link, but you can also reference the picture below:

In Insertion Sort, the left part of the array is sorted an the right part is unsorted. Any standalone element is technically sorted. Thus, we treat str[0] as sorted and move on to str[1], which is why we start our for loop on line 18 at 1.

On line 19, we check to see if str[i-1] > str[i], meaning that we want to see if the element to the left of element i is bigger. If it is, our array is not yet sorted.

So, we have to move the value of str[i-1] to the spot of str[i] and then see if str[i-2] is also bigger than our original str[i]. Until str[i-n] is less than str[i], or we reach the left end of the array, we must keep shifting elements to the right.

The while loop accomplishes the shifting and will continue to do so until we have shifted the last element that is greater than hold, our temporary variable for the original str[i].

That's all there is to it!

C++ Implementation

Before we start, I just want you to know that all the vector<char> stuff is simply a C++ dynamic array.

Go here for the source code or see the screenshot below.

Ignore main(), as that is just the gathering of input. Focus on insertionsort(...), which takes an array (vector) as its only parameter.

We do pretty much the same thing here as we did in Ruby. All that really changes is the syntax and that I called our array vec instead of str.

So, look at the comments and read what I wrote for the Ruby implementation.

Conclusion

That's all for Insertion Sort. I encourage you all to run the programs yourselves and type them out to increase your understanding.

Next time I will be talking about Selection Sort, but not before a little gift of Bogo Sort!

Keep on hacking,
oaktree