JavaScript Algorithms - 23 - Insertion Sort Solution

📱 Follow Codevolution

Insertion Sort Solution
JavaScript Algorithms
Algorithms with JavaScript

[cassettte]

Codevolution is my favorite channel for all things JavaScript.

[asr]

The most intuitive explanation and coding of the insertion sort I've found. Many thanks for helping me understand this! I'll follow your advice and trace the operations with a pen and paper later today.

[ericgerard]

If someone wants to see some logs :)

function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let numberToInsert = arr[i];
let previousIndex = i - 1;

console.log(`
> enters for loop
Current array: ${arr}
NTI: ${numberToInsert} at position ${i},
Previous Element: ${arr[previousIndex]} at position ${previousIndex}`);

while (arr[previousIndex] > numberToInsert) {
arr[previousIndex + 1] = arr[previousIndex];

console.log(`
>> enters while loop:
Copy ${arr[previousIndex]} to position ${previousIndex + 1}
Temporary array : ${arr}
Temporary Previous Element: ${arr[previousIndex]} at position ${previousIndex}`)

// updates previousIndex only inside the while loop (and prevents infinite loop)
previousIndex = previousIndex - 1;
console.log(`
If ${numberToInsert} is greater than ${arr[previousIndex]} at position ${previousIndex}, exit while loop`);
}

arr[previousIndex + 1] = numberToInsert;

console.log(`
Inserts number ${numberToInsert} at position ${[previousIndex + 1]}
NEW loop array: `, arr);
}
}

[janmatousek]

I have used two for loops instead:

const insertionSort = (arr) => {
for (let i = 1; i < arr.length; i++) {
let temp = arr[i];
for (let k = i - 1; k >= 0; k--) {
if (arr[k] > temp) {
arr[k + 1] = arr[k]
arr[k] = temp
} else {
arr[k + 1] = temp
break;
}
}
}
return arr;
}

[anuragkumar]

1 . outer for loop from 1 to n, since 0 is considered sorted and each element in unsorted half(0 to 0) needs to be compared to sorted half (1 to n)
2 . inner loop checks in descending order of index : j to 0 th index
if element at j is greater than the to be inserted element, it is replicated untill a suitable position is found,
then element to be inserted is put at the left duplicate value. Arr [j+1] = to be inserted.

[juanferrer]

I really enjoy this playlist. Great job!
I leave my solution, I think it's a little bit simpler.

const insertion = (array: number[]) => {
for (let i = 1; i < array.length; i++) {
for (let j = i; j > 0; j--) {
if (array[j] > array[j - 1]) break;
[array[j - 1], array[j]] = [array[j], array[j - 1]];
}
}
return array;
};

[mindspray]

Thank you again for this. Solving the problems before moving on and seeing your solution has helped my understanding immensely. I almost had the same solution, i just added an extra if conditional but otherwise was fairly similar.

[devinci]

am i dumb or what this is so confusing to me

[ZaidBinTariq-uf]

My Solution:
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
for (let j = 0; j < i; j++) {
if (arr[j] > arr[i]) {
let numberToInsert = arr[i];
arr[i] = arr[j];
arr[j] = numberToInsert;
}
}
}
return arr;
}

console.log(is([8, 20, -2, 4, -6]));

[sumitkumarsharma]

Thanks for valuable content. I am waiting for long time for react testing library tutorial from you. God bless you. Once again thank you so much for all your tremendous tutorial due which i got job.

[officiallydheeraj]

The best way to understand these sorting algorithms is to dry run the algorithm on your own. I meant to say write down each step.

[abdullah-ayyash]

I came up with a different solution. It's a bit longer than your code but I wrote it before watching your solution:
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let NTI = arr[i];
for (let j = i - 1; j >= 0; j--) {
if (arr[j] > NTI) {
arr[j + 1] = arr[j];
if (j === 0) {
arr[j] = NTI;
}
} else if (arr[j] < NTI) {
arr[j + 1] = NTI;
break;
}
}
}
}

[guddetiajaymanikanta]

I have written the code as below.

const log = console.log;

const getInsertionSortedArray = (inputArray) => {
for(let i = 1; i < inputArray.length; i++) {
let nti = inputArray[i];

for(let j = i; j > 0; j--) {
if(inputArray[j-1] > nti) {
inputArray[j] = inputArray[j - 1];
}else {
inputArray[j] = nti;
break;
}
}
}

log(inputArray);
return inputArray;
}


const inputArray = [-6, 20, 8, -2, 4, 35, 9];

[elmokhtar]

function insertionSort(array) {
for(let i = 1; i < array.length; i++) {
for(let j = 0; j < i; j++) {
if(array[i] < array[j]) {
[array[j], array[i]] = [array[i], array[j]];
}
}
}
return array;
}

[washingtoncampos]

One thing that i didn't understand was one of the concepts of insertion sort is "Assume that the first element is already sorted and remaining elements are unsorted", in this example you gave with the array [8, 20, -2, 4, -6], the first element(8) is not sorted, so this was a bubble sort solution instead of a insertion sort, right?

[crazymallu]

can we use 2 nested for loop?
function insertionSort(arr){
for(let i=1; i<arr.length; i++){
for (let j =0; j<i; j++){
if(arr[j]>arr[i]){
let temp = arr[i]
arr[i]= arr[j];
arr[j]= temp
}
}
}
return arr
}

let array = [-6, 30, 8, -2, 4];

this both are same right?

[ivan]

Great video as always!
But I don't get it with the Big-O calculation - the nested loop dosn't iterate through the whole array but only from i-1 to 0, which means Big-O = O(n^2/2). Am I wrong?

[stevenedwards]

It always gives me "undefined" writing the code exactly as you do, unless I add a "return arr;" add the end of the function. Are you using some sort of extension?

[peteremmanuelkitsamba]

04:50 if this was hard to follow, it is hard to follow🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣

[armoredchimp]

My solution: function insert(arr) {
let length = arr.length;
let sorted = [arr.shift()];
while (sorted.length < length) {
if (sorted[sorted.length - 1] > arr[0]) {
sorted.unshift(arr[0]);
arr.shift();
} else {
sorted.push(arr[0]);
arr.shift();
}
}
console.log(sorted);
return sorted;
}