InsertionSort

reference

Insert sort algorithm idea

The loop array is compared forward from the second element, and if it meets the criteria (larger or smaller than the previous one), it swaps places and eventually “inserts” into the appropriate place.

Insert sort animation

Code Implementation (JS)

const arr = [9.7.8.2.5.1.3.6.4]

function InsertionSort(arr) {
  for (var i = 1; i < arr.length; i++) {
    var j = i
    while (j > 0) {
      if (arr[j] < arr[j - 1]) {
        [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
      } else 
        break
      }
      j--
    }
  }
}


InsertionSort(arr)

console.log(arr) //[1, 2, 3, 4, 5, 6, 7, 8, 9]
Copy the code

Shell Sort

reference

Hill sort, also known as reduced incremental sort, was proposed by DL.Shell in 1959, hence its name. It’s a kind of insertion sort, optimized for insertion sort.

Hill sort algorithm idea

With insertion sort, by comparing elements spaced a certain distance apart (increments), the distance used for each comparison shrinks as the algorithm progresses until adjacent elements are compared.

Hill sort time complexity is O(n^(1.3-2)) and space complexity is constant order O(1). Hill sort is not as fast as the O(n(logn)) quicksort algorithm, so it performs well for medium size, but is not optimal for very large data, and in general is much faster than the O(n^2) algorithm.

Hill sequence diagram

  • (1) Initial increment first gap = length/2 = 4

  • (2) For the second trip, the increment is reduced to 2

  • (3) In the third run, the increment is reduced to 1 and the final ranking result is obtained

Code Implementation (JS)

const arr = [7.6.9.3.1.5.2.4.0]

function ShellSort(arr) {
  var len = arr.length
  for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (var i = gap; i < len; i++) {
      var j = i
      var tmp = arr[j]
      if(arr[j] < arr[j - gap]){
        while (j - gap >=0 && tmp < arr[j - gap]) {
          arr[j] = arr[j - gap]
          j -= gap
        }
        arr[j] = tmp
      }
    }
  }
}

ShellSort(arr)

console.log(arr) // [0, 1, 2, 3, 4, 5, 6, 7, 9]
Copy the code