This is the 17th day of my participation in the August Challenge

Insertion sort

  • Insertion sort: each rowaItem that builds the final sorted array.
  • How to do this: Assume that the first item is already sorted, and then compare it to the second item to determine whether the second item should stay in place or be inserted before the first item. That way, we have the first two items sorted correctly, then compare them to the third item (to determine if it should be inserted first, second, or third), and so on.

implementation

function insertSort(arr) {
    // Declare the required variables
    let len = arr.length;
    let j = null;
    let temp = null;
    // Iterate over the array to sort, as we did above:
    for (let i = 1; i < len; i++) {
        // Assuming that the first item is sorted, the item to be sorted is the second item in the array with index 1 (this is why we start the loop at 1), and we cache the sorted value in the temp variable so that we can insert it into the correct position later
        j = i;
        temp = arr[i];
        // As long as j is greater than 0 (the array index is at least 0) and the value of the previous item in the array is greater than the value being compared, then we move the value to the current position and decrease j
        while (j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j-1]
            j--
        }
        // Finally insert temp into the correct position
        arr[j] = temp
    }
}
Copy the code

parsing

  • Let’s say the array to be sorted is[3, 5, 1, 4, 2]
  1. So let’s say 3 is sorted, and we start with the second item in the array, 5, 3 is less than 5, so 3 stays in place.
  2. And then I becomes 2, and I assign it to j, so now we’re comparing 5 and 1, 5 is bigger than 1, so we switch them, so we subtract j by 1, so we’re comparing 3 with 1, 3 is bigger than 1, we switch them, j minus 1, so now j is equal to 0, Break out of the while loop, and place temp (1) to be sorted at j, the 0th bit in the array. The temporary order to this array is[1, 3, 5, 4, 2]
  3. Then loop through the array again, at this time I is 3, according to the above steps, the array at the end of this round is[1, 3, 4, 5, 2]
  4. And then I is 4, and I get an array of 4[1, 2, 3, 4, 5], so the array sort is complete.