Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Insertion sort, selection sort and bubble sort are two layers of traversal, the time complexity is O(n²); Both of them operate on the original array, so there is no need to create additional array memory space, and the space complexity is O(1).

Insertion sort

  • The idea of insertion sort is to divide the same array into ordered and unordered parts, and insert the unordered part into the ordered part each time. If you have the following array, the green part represents the ordered part and the purple part represents the unordered part



    At this point, element 12 is compared with 45, 42 and 23 in turn, and their positions are changed one by one. Finally, 12 stops more than 11, so it is inserted between 11 and 23.

  • code

        let arr = [3.1.2.4.5.6]
    const insertionSorter = function (arr) {
    // The first element of the array is ordered by default, so it is unordered from I =1
        for(let i = 1; i < arr.length; i++) { // The outer loop is for each unordered element starting with I =1
            for(let j = i; j > 0; j--） { // The inner loop compares individual unordered elements one by one with each ordered element, swapping places
                if (arr[j] < arr[j - 1]) {
                    let temp = arr[j - 1]
                    arr[j - 1] = arr[j]
                    arr[j] = temp
                } else {
                    break
                }
            }
        }
    }
    insertionSorter(arr) // [1, 2, 3, 4, 5, 6]
Copy the code

  • Optimization: When elements are switched, each element is accessed twice (ARR [J-1], ARR [j]), comparing performance consumption. The way to optimize from this point of view is to use the assignment move method, which has the following array: the green part is ordered, the purple is unordered, the current element to be inserted is 12, and the variable temp is used for temporary storage,



    12 is first compared to 42, which moves to the right (assign)

    Compare 12 to 23, 23 moves to the right (assign), and compare to 16, 23 moves to the right (assign)



    At the end of the loop, insert the index position j



    So use assignment (elements are accessed only once) instead of element substitution to reduce the number of accesses and improve performance

        const insertionSorter = function (arr) {
        for(let i = 1; i < arr.length; i++) {
            // Record the element to be inserted
            let temp = arr[i]
            let j
            for(j = i; j > 0; j--） {
                if (temp < arr[j - 1]) { // The element to be inserted, temp, is compared with the previous element
                    arr[j] = arr[j - 1] // The larger element moves to the right, and the element is accessed only once
                } else {
                    break}}// After the inner loop, find the position where the element was inserted
            arr[j] = temp
        }
    }
Copy the code

Selection sort

  • Select the sorting idea is to find the smallest element in the array, and then swap with the first element of the array, and then find the smallest element in the array except the first element, and then swap with the second element of the array, and so on, and finally complete the sorting 
        let arr = [3.1.2.4.5.6]
    const selectionSorter = function (arr) {
        for(let i = 0; i < arr.length; i++) { // The outer loop controls each position swap
            let minIndex = i // Set the initial minimum index
            for(let j = i + 1; j < arr.length; j++) { // The inner loop finds the minimum value of the current remaining element, so the remaining element index traverses from I +1
                if (arr[j] < arr[minIndex]) {
                    minIndex = j
                }
            }
            // The minimum values are interchanged with the array elements in I order
            let temp = arr[i]
            arr[i] = arr[minIndex]
            arr[minIndex] = temp
        }
    }
    selectionSorter(arr) // [1, 2, 3, 4, 5, 6]
Copy the code
  • Optimization (to be updated)

Bubble sort

  • Bubble sort of way of thinking is to each of the elements in an array of compared with other elements, if the value is large, then its swap position, and then compared with the next element, if still more, continue to swap positions, and so on, if this element is one of the biggest, so this element will be “bubble” to the array at the end of the first round is over. Following this logic, the second element is compared to the rest of the array for a second round, and then a third round, and then a fourth round, until the array has been traversed and sorted. 
        let arr = [3.1.2.4.5.6]
    const bubleSorter = function (arr) {
        for(let round = 1; round < arr.length; round++) { // round is a round
        let compareTimes = arr.length - round // The number of comparisons per round
            for(let i = 0; i < compareTimes; i++) { 
                if (arr[i] > arr[i+1]) { // If the value is larger, swap places with the latter element
                    let temp = arr[i]
                    arr[i] = arr[i+1]
                    arr[i+1] = temp
                }
            }
        }
    }
    bubleSorter(arr) // [1, 2, 3, 4, 5, 6]

Copy the code
  • Optimization:If the element position is not performed once in a round traverse, indicating that the array has been sorted, the traversal can be terminated in advance 
        const bubleSorter = function (arr) {
        for(let round = 1; round < arr.length; round++) {
            let hasSwap = false // Marks that this round of bubbling did not swap
            let compareTimes = arr.length - round
            for(let i = 0; i < compareTimes; i++) {
                if (arr[i] > arr[i+1]) {
                    let temp = arr[i]
                    arr[i] = arr[i+1]
                    arr[i+1] = temp
                    hasSwap = true // True if swapping occurs}}if(! hasWeap)break // Exit traversal}}Copy the code

note

  • In terms of consumption time, the performance of the three kinds of sorting are respectively insertion sorting > selection sorting > bubble sorting
  • If there are multiple elements with equal values, the original position may change after using selection sort, such as [2,1,1,3], after sorting [1,1,2,3], the sequential position of the two 1’s may change, but bubble sort and insert sort remain unchanged