Sorting Algorithms: Insertion Sort
Tags: algorithms, codenewbie, womenintech, programming
Published: 2021-04-05 17:03:57

In this next series of Sorting Algorithms, I will be talking about __Insertion Sort__!

## What Is Insertion Sort?
Insertion Sort is a sorting algorithm that consumes an input element for each repetition and grows a sorted output. How this works is, at each iteration, the algorithm removes/ holds one element from the array, looks for the location it belongs to within the sorted list, and _inserts_ that element back into the array at the correct sorted index.
{% youtube OGzPmgsI-pQ %}
***
### Pseudocode
- Start by picking the second element in the array.
- Compare the second element with the element before i. Swap if that second element is greater than the one before i.
- Continue to the next element, and if it is in the incorrect order, loop through the sorted portion, (the left side) to place that element in the current place.
- Repeat till array is sorted. 

***

### The Code With Comments
```javascript
function insertionSort(arr){
  //start looping at first index
  for(var i = 1; i < arr.length; i++){
    //assign a plae holder varible at the index of i to keep track f the value we are looking at
    var currentVal = arr[i]
    //start working backwards with variable j at the value behind i 
    // ex: if i = 9, we want to start comparing the value of i to the value of j --> j = 77
    //we need to keep going while j is greater than 0 (his up to the beginning of the array)
    //and while j is greater than currentVal variable 
    for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
          //ex: is currentVal = 9 smaller than arr[j] = 77 value, yes! then move arr[j] up in the array 
          //[2,4,5,20,77,77]            9 is waitning for its placement
      arr[j + 1] = arr[j]

    }
    //after the loop is done, we have found our placement for currentVal
    //we assign arr[j + 1] to currentVal b/c there will be a duplicate of arr[j] where it was before 
    //       j
    // [2,4,5,20,20,77]          9 waiting
    //       j+1 --> this is where 9 should be now
    arr[j + 1] = currentVal 
  }
  return arr
}
insertionSort([2,4,5,20,77,9])
```

### The Code Without comments
```Javascript
function insertionSort(arr){
  for(var i = 1; i < arr.length; i++){
    var currentVal = arr[i]
    for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
      arr[j + 1] = arr[j]
    }
    arr[j + 1] = currentVal
    
  }
  return arr
}

insertionSort([2,4,5,77,1,9])
```
***
### The Explanation
Now, if sorting algorithms have got your mind all boggled up, don't worry, I was the same way when I first started learning. 

Basically, we want to iterate over the array with our variable i at the first index. _By first I mean the index of array[1]_. We then assign that element into a variable called __currentVal__. 

Now we need to start thinking about how we will be moving backward in our array. We do this by iterating through our array again with a variable j __at the index behind i__. During this loop, if the current value is smaller than arr[j], we need to move it hold on to that value you, go down the list of elements, and find the index it belongs to. 
```javascript
  for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
      .....
    }
```
Our j variable does this by shifting the larger value elements up in the array. 
```javascript
 arr[j + 1] = arr[j]
```
Once we find that our currentVal variable is actually larger than an element at arr[j] we move up by one in the array and assign currentVal to that index
```javascript
    arr[j + 1] = currentVal
```
Finally, out of the loop, we can return the sorted array.

***

### Time & Space Complexity
The _best-case scenario_ for a sorting algorithm like insertion sort is O(n).
We can obtain this during each iteration, the first remaining elements of the input is only compared with the right-most element of the sorted subsection f the array. This is achieved by using a while loop instead of a nested for loop.

Now, the _worst-case senario_ for insertion sort is O(n^2), which is a quadratic running time. That is because, there is a nested for loop, which is looking through our array backward. Looking through and shifting the sorted subsection of the array before inserting the element into its right position.

### The Conclusion
Now, even though Insertion sort is much more efficient & faster than Bubble sort and Selection sort when it comes to small array lengths. It can not handle a large list of arrays. However, there are more advanced sorting algorithms that I will diving into next time on this series of __Sorting Algorithms__! So Stay tuned for the next blog post :)

Happy Coding! 
***
### References
[Learn more about Insertion sort](https://en.wikipedia.org/wiki/Insertion_sort#Best,_worst,_and_average_cases)