Insertion Sort Algorithm - 401-advanced-javascript-jonnygraybill/data-structures-and-algorithms GitHub Wiki
Insertion Sort
What is it?
The insertion sort method is a way of sorting arrays, basically by dividing it into two different sections - sorted, and unsorted. From there, you compare what is sorted against what is unsorted, and swap index positions as you go along.
Visual
Pseudo Code
InsertionSort(int[] arr)
FOR i = 1 to arr.length
int j <-- i - 1
int temp <-- arr[i]
WHILE j >= 0 AND temp < arr[j]
arr[j + 1] <-- arr[j]
j <-- j - 1
arr[j + 1] <-- temp
Algorithm
It starts with a for loop that begins at position 1 of the index (the second position in an array), iterates over the entire length of the array, and increased one index position each loop.
variable "j" gets assigned as "i" minus one. Meaning whatever index position "i" is at a given point, "j" will be one behind it. We will also instantiate a "temp" variable, assigned as the value of the position of the array that "i" is currently on. Now we are ready to begin our while loop - which is where the magic happens!
While "j" is less than or equal to 0 (remember "j" is just the index position of "i" minus one, AND temp (the value of the index position that "i" is on) is less than the value of whichever index position "j" is at, we'll progress forward. If either or both of these conditions are false, we'll go to the next iteration of our parent for loop.
If both the previously defined conditions are true, we are going to assign the value of index position "j" + 1 to the value of index position "j." Then we are going to assign j's index position to "j" minus 1. Then, we assign the value of the index position "j" + 1 to "temp." This will perform the swap, and it will continue like this until one or both of our conditions for our while loop are no longer true.
function insertionSort(arr){
for(let i = 1 ; i < arr.length ; i++){
let j = i - 1;
let temp = arr[i];
while( j >= 0 && temp < arr[j]){
arr[j + 1] = arr[j];
j = j - 1;
arr[j + 1] = temp;
}
}
return arr;
}
insertionSort([9,8,7,6]);