Skip to content

Instantly share code, notes, and snippets.

@abuseofnotation
Last active December 14, 2020 21:04
Show Gist options
  • Save abuseofnotation/8cb542c026396e9d412206e1fcc7c050 to your computer and use it in GitHub Desktop.
Save abuseofnotation/8cb542c026396e9d412206e1fcc7c050 to your computer and use it in GitHub Desktop.
Insertion sort implementation in JS
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