This is the tenth day of my participation in the August More Text Challenge. For details, see “August More Text Challenge”.

Yesterday, the last chapter, we talked about algorithms, and the classic algorithm called bubble sort, and today we’re going to talk about selection sort and insertion sort.

Selection sort

Selection sort, like bubble sort, does not perform as well in comparison, but is simple to implement.

Select the sorting idea

  • Find the smallest value in the array, select it and place it first.

  • Then find the second smallest value, select it and place it in second place.

  • In the same way, N – 1 rounds are performed to complete the sorting.

Select the sort of animation

As shown in the animation:

  • Red is the smallest element in the current loop.

  • Green is the element where the current loop is located.

  • Yellow is the sorted element.

Select sort animation

implementation

The code is as follows:

Array.prototype.selectionSort = function () {
    for (let i = 0; i < this.length - 1; i++) {
        let indexMin = i
        for (let j = i; j < this.length; j++) {
            if (this[j] < this[indexMin]) {
                indexMin = j
            }
        }
        if(indexMin ! == i) {const temp = this[i]
            this[i] = this[indexMin]
            this[indexMin] = temp
        }
    }

}
const arr = [3.44.38.5.47.15.36.26.27.2.46.4.19.50.48]
arr.selectionSort()
console.log(arr);
/ / /
   2.3.4.5.15.19.26.27.36.38.44.46.47.48.50
]

Copy the code

Select the time complexity of the sort

  • Two nested loops.

  • Time complexity: O(n^2).

Insertion sort

Insertion sort is the same complexity as bubble sort, selection sort, but for sorting small arrays, insertion sort is much better.

Insert sort idea

  • Start with the second number and go forward.

  • If you’re bigger than that, go to the back.

  • And so on to the last number.

Insert sort animation

Insert sort animation

  • Red is the element that comes out.

  • Green is the element that is currently being compared.

  • Yellow is the sorted element.

implementation

Array.prototype.insertionSort = function () {
    for (let i = 1; i < this.length; i++) {
        const temp = this[i]
        let j = i
        while (j > 0) {
            if (this[j - 1] > temp) {
                this[j] = this[j - 1]}else {
                break
            }
            j--
        }
        this[j] = temp
    }
}
const arr = [3.44.38.5.47.15.36.26.27.2.46.4.19.50.48]
arr.insertionSort()
console.log(arr);
/ / /
   2.3.4.5.15.19.26.27.36.38.44.46.47.48.50
]
Copy the code

The time complexity of insertion sort

  • Two nested loops.

  • Time complexity: O(n^2).

End~~~