Insertion Sort
How it works
- Insertion sorting algorithm starts iteration with choosing the one input element from the array,
- In every iteration, the insertion sorting algorithm moves the one element from the input array to the sorted array by finding its location where it shall be,
- It repeats until no input elements left in the input array
Performance
- Best case perfoarmace: Time complexity O(n),
- Averagecase performance: Time complexity O(n2),
- Worstcase performace: Time complexity O(n2),
Implement insertion sort
Lets implement the insertion sort in Javascript
/ insertion sort in javascript
const insertionSort = (param) => {
if (param) {
let sizeOfArray = param.length;
for (let i = 1; i < sizeOfArray; i++) {
let inputElement = param[i];
let j = i - 1;
while (j >= 0 && param[j] > inputElement) {
param[j + 1] = param[j];
j = j - 1;
}
param[j + 1] = inputElement;
}
return param;
}
};
let sortedArray = insertionSort([5, 3, 6, 7, 2, 1]);
console.log(sortedArray);
// output
// [1, 2, 3, 5, 6, 7]