I'm looking at the insertion sort algorithm, which is correctly implemented with the below code, but I don't understand how the while loop does its job:
const arr = [8, 20, -2, 4, -6];
insertionSort(arr);
console.log(arr); // [-6, -2, 4, 8, 20]
function insertionSort(arr) {
// Two loops, outer to look at each element, and inner to shift elements
// Outer loop
for (let i = 1; i < arr.length; i++) // i starts at 1 because we don't need to sort the first element
{
let key = arr[i];
let j = i - 1;
// Inner loop
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}I don't understand how the while loop achieves that the array gets sorted. It just seems to copy values, while I would expect values to be swapped. How can that work?
It may help to distinguish two partitions in the array:
At the start of an outer iteration, the value of i represents the index at which the second partition starts. It can start at 1, because that means the left partition has just one value, and a list with just one value is sorted (obviously).
Each iteration of the outer loop grows the sorted partition with one element, and shrinks the other partition by one. This continues until the sorted partition has all elements of the array (and the right-side partition is empty).
Before the inner loop starts, we can assume the left partition has grown to include the element at index i, i.e. key, but this value may not be at the right position in that sorted partition, and that is what the inner loop will fix:
The goal of the inner loop is to find the right spot in the sorted partition for the key value that currently might sit at the wrong position. While looking for that spot, it also moves the values it encounters one place to the right. In so doing it foresees an insertion spot where key can be written to.
When the inner loop ends, j + 1 is the index where key belongs within the (grown) sorted partition.
Let's say we have already made some iterations of the outer loop, and start a new iteration with i equal to 5, and have this state of the array:
sorted | unsorted
|
[2, 5, 8, 12, 15, 7, 1, 11, 6]
| ↑
| i=5
Then the following happens:
The value at index i is saved in the variable key, and that index is now considered an empty slot (it is not really emptied, but it helps to see it that way):
sorted | unsorted
|
[2, 5, 8, 12, 15, --, 1, 11, 6]
↑ |
j | key: 7 (must be inserted in sorted partition)
The inner loop starts at j=4 and walks back moving values one position to their right (into the "gap") for as long as necessary. After a few iterations we get:
sorted | unsorted
|
[2, 5, --, 8, 12, 15, 1, 11, 6]
↑ |
j | key: 7 (must be inserted in sorted partition)
At this point it is the first time we encounter a value at index j that is less than key, and so that loop exits. The gap is now at index j+1, and that is where the value key belongs.
sorted | unsorted
|
[2, 5, 7, 8, 12, 15, 1, 11, 6]
↑ |
j |
I hope this clarifies it.