This is the 6th day of my participation in the August More Text Challenge

Insertion sort

Insertion sort is a simple sorting algorithm. Insertion sort divides a set of data into ordered interval and unordered interval. Every time, a suitable data is found from the unordered interval and inserted into the appropriate position of the ordered interval.

Algorithm description

Let’s say I’m going from smallest to largest

1. The first data of a set of data form an ordered interval, and the other data form an unordered interval
2. Extract the first data A from the unordered interval
3. A is compared with each data in the ordered interval in turn. If it encounters data larger than A, A is inserted to the previous position of the data, and if A is larger than any data in the ordered interval, it is inserted to the end of the ordered interval. Anyway, make sure that the ordered interval is still ordered after insertion.
4. Repeat operations 2 and 3 until the unordered interval has no data

Algorithm diagram

Suppose a set of data has: 3, 5, 4, 1, 2.

In the “First insertion” step, 3 is an ordered interval, and 5, 4, 1, and 2 are unordered intervals. 5 is larger than 3. Since there is no more data behind the ordered interval, 5 is inserted after 3 in the ordered interval.

In the “second insertion” step, 3 and 5 are the ordered intervals, and 4, 1 and 2 are the unordered intervals. The first data 4, which marks the disordered interval, is compared with 3 of the ordered interval. 4 is larger than 3, so it needs to continue to compare with the next data. 4, in contrast to 5 in the ordered interval, is less than 5, so 4 is inserted before 5 in the ordered interval.

The “third insert” step, again, marks the first data of the unordered interval, 1, 1, compared to the ordered interval, 3, 1 is less than 3, and is inserted before 3.

In the “fourth insert” step, the unique data 2 of the unordered interval is larger than 1 of the ordered interval and smaller than 3 of the ordered interval, so it is inserted in front of 3. At this point, the whole set of data is perfectly ordered.

Do you notice how insert sort is a lot like poker?

The card in the hand is an orderly interval, the pile of cards on the table is a disorderly interval, each time when drawing cards, are to be compared with each card in the hand in turn, and the card is inserted into the corresponding position, to ensure that the card in the hand is orderly. When the deck is empty, the entire deck is in order.

Code implementation

Note: although it is necessary to divide the data into ordered and unordered ranges, it is not necessary to apply two arrays (ordered and unordered array) in the implementation, just abstract partition in the original array.

// Insert sort
function insertionSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  for (var i=1; i<arr.length; i++) {
    var j = i - 1 // j is the largest subscript of the ordered interval
    var val = arr[i] // val is the first value of the unordered interval and is used to compare the values of the ordered interval
    for (; j>=0; j--) {
      if (arr[j] > val) { // If val is smaller than arr[j], val needs to be sorted before arr[j], and arr[j] needs to be shifted
        arr[j+1] = arr[j]
      } else {
        break // When no shift is needed, the ordered interval is ordered, so just jump out of the loop
      }
    }
    arr[j+1] = val
  }
  return arr
}
Copy the code

Insert sort can actually be improved and optimized, and the optimized version of insert sort is called Hill sort, which I’ll talk about later.

Js algorithm series articles recommended

• Js algorithm – Bubble sort (juejin. Cn)