Loading content…
Sorting Algorithms
Insertion Sort grows a sorted prefix and inserts each new element into its correct position.
The algorithm moves from left to right and treats the beginning of the array as an already sorted segment.
Each new element is compared with previous values and shifted left until it reaches the correct insertion point.
It is simple, stable, and especially effective on nearly sorted or very small inputs.
This implementation swaps the current value backward until it lands in the correct place inside the sorted prefix.
// Проходим все элементы и на каждой итерации
// сравниваем текущий элемент с предыдущими и так до самого начала,
// если текущий меньше предыдущего в паре, то меняем их местами.
// O(n^2)
function insertionSort (arr) {
for (let i = 0; i < arr.length; i++) {
let j = i;
while (j > 0 && arr[j-1] > arr[j]) {
const tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
j = j - 1;
}
}
return arr;
}