Have you ever had a classic algorithm that you thought was clear in the class, but forgot after a while?

This series of articles attempts to address that question.

Read up on the sorting algorithms, read up on their names, and they’re all very aptly named.

Insert sort, for example, refers to inserting elements to be sorted into a sorted sequence.

The figure above illustrates the fourth iteration, where elements 1, 3, and 5 are already in an ordered sequence, and element 2 is to be inserted between 1 and 3. So now the 3 and the 5 have moved back one place.

It can be seen that the core of the algorithm is: how to find the correct insertion position in the ordered sequence?

The idea is to start at the end of an ordered sequence and compare it one by one with the target element. If it is larger than the target element, the element needs to be moved back.

You can see that the reason for caching the target first is to leave its location empty so that other elements can move in. In addition, when the element is no larger than the target, the location to insert the target has been found.

Translated into code:

let array = [1.3.5.2.4]
let i = 3
let target = array[3]
while(i > 0 && array[i- 1] > target) {
  array[i] = array[i- 1]
  i--
}
array[i] = target
console.log(array) // [1, 2, 3, 5, 4]
Copy the code

If you can insert one successfully, iterate n-1 times (the first element is itself an ordered sequence), you can insert all of them, and the code is easy to write:

for (let j = 1; j < array.length; j++) {
  let i = j
  let target = array[i]
  while(i > 0 && array[i- 1] > target) {
    array[i] = array[i- 1]
    i--
  }
  array[i] = target
}
Copy the code

See the full code: codepen.

So far, the principle and implementation of insert sort are covered.

To sum up, insertion sort does not need extra space, is a local sort, equal elements do not exchange the order, so it is stable sort, time complexity O(n^2), suitable for small data sort. Insertion sort is used more than bubble sort and selection sort. Because the first two are commutative sorts, they essentially require three atomic operations.

Insert sort, to be able to write it out in minutes, is the need to master the sorting principle. The core of each traversal is to find the correct insertion position. Once the inner traversal can be written down, the whole is easy to write down. There is no need to memorize.

Hope to help, the end of this article.


Articles in this series have been published:

  • Handwriting Algorithms and Remember it: Bubbling Sort
  • Handwriting Algorithms and Remembering them: Sorting by Choice