Javascript Algorithm:Insertion Sort(FreeCodeCamp)

Implement Insertion Sort:

The next sorting method we'll look at is insertion sort. This method works by

building up a sorted array at the beginning of the list. It begins the sorted

array with the first element. Then it inspects the next element and swaps it

backwards into the sorted array until it is in sorted position. It continues

iterating through the list and swapping new items backwards into the sorted

portion until it reaches the end. This algorithm has quadratic time complexity

in the average and worst cases.

Instructions:

Write a function insertionSort which takes an array of integers as input and

returns an array of these integers in sorted order from least to greatest.

Test Cases:

1) insertionSort should be a function.

2) insertionSort should return a sorted array (least to greatest).

3) insertionSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92])

should return an array that is unchanged except for order.

4) insertionSort([5, 4, 33, 2, 8]) should return [2, 4, 5, 8, 33].

5) insertionSort should not use the built-in .sort() method.

Solution:

function insertionSort(array) {

let newArray = [];

newArray.push(array[0]);

for (let i = newArray.length; i < array.length; i++) {

newArray.push(array[i]);

let k = newArray.length - 1; //index of newly inserted element

let j = k - 1;

while (j >= 0) {

if (newArray[k] < newArray[j]) {

[newArray[k], newArray[j]] = [newArray[j], newArray[k]];

k = j;

j = k - 1;

} else {

j = j - 1;

}

}

}

return newArray;

}

let result = insertionSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,

92]);

console.log(result);