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))

--

--

--

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

Recommended from Medium

Autogenerating clients with FastAPI and Github Actions

This year, set aside ReactJS Development

Think in a React Way

NahamCon CTF 2022 Write-up: Click Me! Android challenge

Beginner’s guide to encoding, encryption and hashing

Performance tuning of redux-react app

JS Interview Questions

Using GraphQL Mutations in Vue.js

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
Woodelin florveus

Woodelin florveus

More from Medium

Must know DBMS Concepts: Beginner to Advanced

Resources to scale any application

Data Structures & Algorithms in JavaScript(Hash Table)

Understanding time and space complexity with Big O