Insertion Sort

Photo by Yaoqi LAI on Unsplash

This week I’m having a look at Insertion sort, another simple method to sort an array. In short, Insertion sort takes one value at the time, and checks it only compared to items to its left. If the item is smaller, it will be swap them until all the numbers to its left are smaller. This means that for each item, all the items to its left will already be sorted.

https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

In practice at each iteration we are dividing the input in two separate arrays. The left array will always be sorted (a number on it’s own it’s sorted) and the right array is waiting to be sorted. We take the item with index = 0, which goes in the sorted array and nothing else needs to be done. Then we take the item with index = 1, which is were we actually start checking who’s bigger/smaller. The item that we compare with the left side of the array is called the key. The key gets compared to all items of the sorted array starting from the last, until the key is also sorted. Then we move to the next index of the initial array and the whole input is sorted. So each key is inserted in the sorted array, hence the name Insertion sort.

https://tamalweb.com/notes-on-algorithms-3-insertion-sort

In pseudo-code:

array = [several items]for (i = 1 to array.length) {
key = array[i]
j = i - 1
while (array[j] > key & j > 0){ // if array[j] is bigger
array[j+1] = array[j] // we move it up one space
j = j - 1
}
array[j+1] = key // we place our key in its sorted spot
}

Example:

Let’s look at the array = [4,2,5,3,1].

We start sorting from index = 1 cause we for each item we need to be able to compare it to the item to its left.

Let’s take that element (2) and compare to the array made of the items to its left, which in this case is only made of one number (4). 2 < 4 so the items are swapped. Now our array = [2,4,5,3,1]. Let’s go through the rest of the array repeating the process until it’s completely sorted.

Iteration 1: comparing the element at index = 1(2) with 4: [4,2,5,3,1] → [2,4,5,3,1]

Iteration 2: comparing the element at index = 2(5) with 4: [2,4,5,3,1] → [2,4,5,3,1]

Iteration 3: comparing the element at index = 3(3) with 5 and 4: [2,4,5,3,1] → [2,4,3,5,1] → [2,3,4,5,1]

Iteration 4: comparing the element at index = 4(1) with 5, 4, 3 and 2: [2,3,4,5,1] → [2,3,4,1,5] → [2,3,1,4,5] → [2,1,3,4,5] → [1,2,3,4,5]

Notice how after each step, all the items to the left of the item that we are comparing are already sorted.

In actual code:

let insertionSort = (array) => {
for (i = 1; i < array.length; i++) {
let key = array[i];
let j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j]
j = j - 1;
}
array[j + 1] = key;
}
return array;
}

Just before the end we assign the value of the key to input[j + 1] because array[j] corresponds to the first item in the sorted array whose value is less than the key’s value, so the key goes to the right of that.

Ta-dah!

They just understood Insertion Sort

That’s it, thanks for reading! Don’t forget to watch Insertion sort if it was Folk dance.

Web developer, always learning

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Unit testing for Vue.js and TypeScript

Mistakes to be Avoided while Developing Apps with Angular!

Creating Invoices in Node.js

Building a React component library with styled-components: Input Field

How to test your Javascript code in Laravel with Jest

Hybrid Testing Approach by using Puppeteer and SuperTest.

Data Structure: Selection Sort

Ten Practices to Avoid being a Java developer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Fedemcmac

Fedemcmac

Web developer, always learning

More from Medium

Debouncing and Throttling in JavaScript

how to master javascript-react!

How to handle asynchronous operations using a callback, promises & async/await in JavaScript

Principles for Coding and JavaScript objects