Let's practice Insert Sort (Javascript)

Show me the code

let data = [8, 6, 10, 5, 3, 9, 2, 7, 4, 1]

function InsertSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let currentIdx = i
        for (let j = i - 1; j >= 0; j--) {
            if (arr[currentIdx] < arr[j]) {
                [arr[currentIdx], arr[j]] = [arr[j], arr[currentIdx]]
                currentIdx = j
            }
        }
    }

    return arr


}
console.log(InsertSort(data))//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

key Idea

The tricky part of this algorithm:

1. Define a currentIdx variable, which is the index the latter will be compared to.

2. The second nested for-loop will have the j index and compare to the currentIdx.

3. Since currentIdx is already assigned to the current Index, i, so the j will be j-1, the previous one, we want to compare.

4. We compare two number side by side. This is part of how this algoritem works.

5. Finally, when the condition match (meaning the arr[currentIdx] < arr[j]), we swap and we need to dynamically rebind currentIdx to j. This is the essential part of this algorithm, which is going to find the previous index spot and swap (or "insert") them.

6. Tip: Try to google "insert sort animation" and have a visual idea of how the algorithm goes.