Everything is compared to every other item, just as it was with bubble sort. It “splices” in the correct order rather than replacing. In other words, it restores the original arrangement of repeated items.
The complexity of Space and Time
Best: O(n) time | O(1) space
Average: O(n^2) time | O(1) space
Worst: O(n^2) time | O(1) space
n is the length of the input array.
Input
[8, 5, 1, 9, 5, 6, 2]
Output
[1, 2, 5, 5, 6, 8, 9]
Hint
Divide the input array into two subarrays; the first subarray should be sorted at all times and while the second subarray should be unsorted. Iterate through the unsorted subarray, inserting all of its elements into the sorted subarray in the correct position by swapping them.
At first, the array will be split into smaller sections. These sections are then combined to form larger ones until eventually the entire array is sorted.
Pseudo Code
DEFINE FUNCTION insertionSort(array): FOR i IN range(1, len(array)): SET j TO i WHILE j > 0 and array[j] < array[j - 1]: swap(j, j - 1, array) j -= 1 RETURN array DEFINE FUNCTION swap(i, j, array): SET array[i], array[j] TO array[j], array[i]
Typescript Code
function insertionSort(array) { for (let i = 1; i < array.length; i++) { let j = i; while (j > 0 && array[j] < array[j - 1]) { swap(j, j - 1, array); j -= 1; } } return array; } function swap(i, j, array) { const temp = array[j]; array[j] = array[i]; array[i] = temp; } mocha.setup("bdd"); describe("Bubble Sort", () => { it("Test Case #1", function () { const input = [8, 5, 1, 9, 5, 6, 2]; chai.expect(insertionSort(input)).to.deep.equal([1, 2, 5, 5, 6, 8, 9]); }); it("Test Case #2", function () { const input = [5, 3, 1, 2, 4]; chai.expect(insertionSort(input)).to.deep.equal([1, 2, 3, 4, 5]); }); }); mocha.run();
Demo
https://codepen.io/evalteam/pen/OJOJGmm
Quick Links
Legal Stuff