Theory: Insertion Sort

Preface

This post will go over an easy to comprehend overview of the Insertion Sort algorithm.  This will be the first sorting algorithm we cover in our Computer Science (CS) Fundamental’s series.

Theory

The Insertion Sort algorithm is what is known as an in-place comparison sorting algorithm.  What is an in-place comparison sorting algorithm?  Well an in-place sorting algorithm is one which performs its operations on the current data structure, without necessitating an external data structure.  In short if you have array A and you would like to perform an Insertion sort on array A, all operations will take place in array A.  You will not be creating a second array or data structure to store the sorted elements.

Why wouldn’t we just use an external data structure?

The main advantage for in-place algorithm’s, is one of efficiency.  In-place algorithm’s are ideal for scenarios in which the device has a memory limitation, as well as one in which fewer I/O cycles are necessary.  I/O can be more expensive than CPU calculation’s.

Insertion Sort

The Insertion Sort functions by assuming that everything to the left of array[i] is already sorted.  In the example of an array containing: 4, 3, 2, 1 everything to the left of the 4 would be considered sorted.  We compare the current element i vs i+1 and if i+1 is out-of-place we will insert it in its correct place on the sorted segment of the array.

Here is a visual representation of the insertion sort, I found this image labeled for re-use and it will help us walk through the algorithm.

Insertion Sort:

 

As we can see at the beginning we have an array with four elements: 4, 3, 2,  1.  We would like to sort this array in an increasing order via an Insertion Sort.  

1. Compare array[0] against the sorted segment of the array to the left.  *No sorted items yet
2. Compare array[1] against the sorted segment of the array to the left against array[0].  3 < 4 therefore we will insert the 3 to the left of the 4.
3. Compare array[2] against the sorted segment of the array to the left against array[1].  2 < 4 therefore we will insert the 2 to the left of the 4.  We then compare the 2 against the element to the left in its new position, to ensure it is in its respective slot.  2 < 3 therefore we will insert the 2 before the three.  At this point everything to the left of array[3] is sorted.
4. Compare array[3] against the sorted segment of the array to the left against array[2].  1 < 4 therefore we will insert the 1 to the left of the 4.  We will now compare the 1 against the element to the left in its new position, to ensure it is in its respective slot.  1 < 3 therefore we will insert the 1 to the left of the three.  We will now compare the 1 against the element to the left in its new position, to ensure it is in its respective slot.  1 < 2 therefore we will insert the 1 to the left of the three, with no remaining elements to the left as 1 is now in array[0] we can conclude that our array is sorted in an increasing order.

Big O

Big O is a topic which we will discuss in detail in a future post, though I will state the Big O for the Insertion Sort.

• Worst-case Running time:
  • Θ(n²)
• Best-case Running time:
  • Θ(n)
• Worst-case swaps
  • Θ(n²)

To be continued

This conclude’s the introduction to Insertion Sort.  In the next part of the Insertion Sort, we will be looking at a live example of the algorithm in JavaScript, along with an explanation.