Data Structure: Insertion Sort

What is Insertion Sort?

In this particular blog, we’ll be talking about the Insertion Sort technique. This method takes elements in random order and sorts them based on the comparison. One way to think about this algorithm from a different perspective is to imagine if you were given a handful of cards, your immediate instinct is to sort them from ascending order. It’s highly intuitive and a comparison-type algorithm. However, the downside would be the time complexity which is O(n²). This method is deemed to be the worst-case scenario.

How Does it Work?

Start with creating an accessible variable called temp.

function insertionSort(array){ 
    let temp;
}

Iterate through the array starting at the index of 1. Within that first iteration well set temp to the current index of the array.

function insertionSort(array){
    let temp;
for(let i = 1; i < array.length; i++){
            temp = array[i]
    }
}

This next step requires iteration, however, there is a particular trick to this because we will be setting a condition within the loop.

We will start with a second iteration, which consists of starting at the index before our first index of the first iteration. Furthermore, we will add a condition of if the index before the current array is greater than the actual current array. It will look more like this.

function insertionSort(array){
    
    let temp;
for(let i = 1; i < array.length; i++){
            temp = array[i]
for(var j = i-1; array[j] > temp && j <-1; j--){
  
       }
    }
}

There is an important trick in this particular loop that is overlooked. The index of j has to be greater than -1. This is implemented because if the loop is continuously comparing and sorting the order of the elements it will eventually go beyond the index of 0 to -1. Therefore we added a condition of the index of j must be greater than -1.

Once the second iteration is established and conditions are met, we will move the index of j over 1 in place of temp.

function insertionSort(array){
    
    let temp;
for(let i = 1; i < array.length; i++){
            temp = array[i]
for(var j = i-1; array[j] > temp && j <-1; j--){
                array[j + 1] = array[j]
            }
     }
}

We will then break out of the for loop and put temp in the open spot. Once everything checks out we will return the array.

function insertionSort(array){
    
    let temp;
for(let i = 1; i < array.length; i++){
            temp = array[i]
for(var j = i-1; array[j] > temp && j <-1; j--){
                array[j + 1] = array[j]
            }
array[j + 1] = temp
        }
    
    return array
}

Here is a full look at the solution below. Hoped you guys enjoyed it till next time.

function insertionSort(array){
    
    let temp;
for(let i = 1; i < array.length; i++){
            temp = array[i]
for(var j = i-1; array[j] > temp && j <-1; j--){
                array[j + 1] = array[j]
            }
array[j + 1] = temp
        }
    
    return array
}
let myInsertion = [1,2,4,3,5,6]
console.log('insertionSort', insertionSort(myInsertion))