concept

The algorithm that sorts the data sequentially from the left end of the sequence is called insertion sort.

The characteristics of

  • The data in the sequence is divided into two regions: sorted region and unsorted region
  • Define the sort area starting at the far left of the sequence
  • Data for sorted regions is arranged in the order of smallest arrival
  • Element comparison is performed by comparing the first element of the unsorted region with the last element of the sorted region

The illustration example

Sort the following data as shown in the figure

  • Assuming that the leftmost number 5 has been sorted, place 5 in the sorted region
  • In the unsorted region, take the leftmost number 3 and compare it to the number in the sorted region.
  • If the left digit is larger, the two digits are swapped and the operation is repeated until either the returned digit is smaller than the removed digit, or the removed digit has been moved to the far left of the entire sequence.
  • The operation is complete, and the sorted numbers are 3 and 5
  • Repeat step 2 to take the number 4 and compare it first with the number 5 in the sorted region
  • 5 is greater than 4, so switch these two numbers. After the exchange, 4 was compared with 3 on the left, and it was found that 3 was less than 4, which conforms to the description in Step 3. The returned number on the left was smaller than the removed number, so the operation ended
  • When the operation is complete, the sorted region numbers are :3,4,5
  • Repeat Step 2, take out the number 7 and compare it with the number 5 in the sorted area first, and find that 5<7
  • When the number taken out is compared for the first time and the number in the sorted area is smaller than the number taken out, no operation is required and the number taken out can be directly put into the sorted area.
  • Repeat until all the numbers are in the sorted area, that is, the sorting is complete.

Implementation approach

  • Declares a function that takes an array
  • Declares an array of unsorted regions and assigns the parameters passed in to the array
  • Declares an array of sorted regions and initializes element 0 of the array to element 0 of an array of unsorted regions
  • Forward traversal of an unsorted array starting at element 1 of the array
  • Adds the currently traversed value to the sorted range
  • Reverse traversal of the sorted region, starting at the penultimate element of the array
  • Gets the position of the currently newly inserted element in the sorted region
  • Size the newly inserted value of the sorted region against the currently traversed element
  • If the newly inserted value is less than the value currently traversed, the position is reversed

Next, we use JavaScript to implement the insertion sort according to the implementation idea.

/* * 1. The default value of the sorted range is element 0 of the array * 2. 3. Add the left-most value of the unsorted region to the sorted region * 4. Reverse traversal of sorted region data * 5. Size comparison between newly inserted data and currently traversed data * 6. If the newly inserted data is smaller than the currently traversed data, the position * */ is switched

const insertSort = function (arr) {
    // Unsorted region
    let unsortedArea = arr;
    // Sorted region
    let sortedArea = [arr[0]].for (let i = 1; i < unsortedArea.length; i++){
        // Sorted region Adds the leftmost value of the current unsorted region
        sortedArea.push(unsortedArea[i]);
        // Reverse traversal of sorted region values to sort sorted region values
        for(let j = sortedArea.length - 2; j >= 0; j--){
            // The position of the current inserted value in the sorted region
            let insertIndex = sortedArea.getArrayIndex(unsortedArea[i]);
            // Size the newly inserted value of the sorted region against the current element loop
            if( unsortedArea[i] < sortedArea[j]){ [sortedArea[insertIndex],sortedArea[j]] = [sortedArea[j],sortedArea[insertIndex]]; }}}return sortedArea;
};

// The prototype adds a lookup index function
Array.prototype.getArrayIndex = function (obj) {
    for(let i = 0; i <this.length; i++){if(this[i]===obj){
            returni; }}return - 1;
};

const arrData = [5.8.9.2.3.6.1.0.7];
console.log(insertSort(arrData));
Copy the code

The execution result

After the above code is executed, there is no problem and it is sorted correctly, but after I change the data, the above code will not work properly.

const arrData = [5.8.9.2.3.6.1.0.7.7.7.7];
console.log(insertSort(arrData));
Copy the code

Correct implementation

Thanks to @_dreams’ correcting, I found the error of my code. The correct code is as follows:

const insertSortOther = function (arr) {
    const len = arr.length;
    for (let i = 1; i < len; i++) {
        let temp = arr[i];
        // The elements are sorted by default
        let j = i - 1;
        // Scan from back to front in sorted queues
        while (j >= 0 && arr[j] > temp) {
            // The sorted element is larger than the new element, move the element to the next position
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
    return arr;
}
Copy the code

Test that the above code executes correctly

const data = [5.8.9.2.3.6.1.0.7.7.7.7];
console.log(insertSortOther(data))
Copy the code

Write in the last

  • The pictures used in this article are from “my first algorithm book”, if infringement, please leave a message in the comment section, the author immediately delete the relevant pictures.
  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
  • This article was first published in nuggets. Reprint is prohibited without permission 💌