Last active
December 14, 2020 21:04
-
-
Save abuseofnotation/8cb542c026396e9d412206e1fcc7c050 to your computer and use it in GitHub Desktop.
Insertion sort implementation in JS
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const array = [1, 2, 10, 5, 4, 0, 9, -1, 3]; | |
const insertionSort = (array: Array<number>) => { | |
for (let i = 1; i < array.length; i++) { | |
const newElement = array[i]; | |
const prevElement = array[i - 1]; | |
// If the current element is smaller than the previous one, | |
// we have to insert it in its proper place | |
if (prevElement > newElement) { | |
console.log('Found an unordered element',newElement) | |
console.log(array); | |
// Go through the portion of the array where the new | |
// element has to be inserted in a reverse order | |
for (let j = i; j >= 0; j--) { | |
const currentElement = array[j - 1]; | |
// If the current element is bigger than the new one | |
// then we still haven't reached the point where the new | |
// element has to be inserted. | |
if (currentElement > newElement) { | |
// Shift the index of the element to make space for | |
// the new one, when its time comes | |
array[j] = currentElement; | |
array[j - 1] = null; // not really needed, but makes things clearer | |
console.log('Searching for a spot:') | |
console.log(array) | |
} else { | |
// When we reached the point where the new element is bigger | |
// then we insert it in the array. | |
// (we already freed the spot in the previous iteration) | |
array[j] = newElement; | |
console.log('Inserting', newElement, ':'); | |
console.log(array) | |
// break out of the loop, we are done here | |
break; | |
} | |
} | |
} | |
} | |
return array; | |
}; | |
console.log(insertionSort(array)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment