Insertion Sort algorithm is a simple and intuitive sorting algorithm. It works by building an ordered sequence, scanning back to front in the sorted sequence for unsorted data, finding the appropriate location and inserting it.

Insertion sort

Insertion Sort algorithm is a simple and intuitive sorting algorithm. It works by building an ordered sequence, scanning back to front in the sorted sequence for unsorted data, finding the appropriate location and inserting it.

Algorithm description:

In general, insert sort is implemented using in-place arrays:

  • Starting with the first element, the element can be considered sorted;
  • Fetch the next element and scan back to front in the sorted element sequence;
  • If the element (sorted) is larger than the new element, move the element to the next position;
  • Repeat step 3 until you find a place where the sorted element is less than or equal to the new element;
  • After inserting a new element into that position;
  • Repeat steps 2 to 5.

GIF demo:

Code implementation:

function Insertion(arr) {
  let len = arr.length;
  let preIndex, current;
  for (let i = 1; i < len; i++) {
    preIndex = i - 1;
    current = arr[i];
    while (preIndex >= 0 && current < arr[preIndex]) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = current;
  }
  return arr;
}
 
 
var arr = [3,5,7,1,4,56,12,78,25,0,9,8,42,37];
Insertion(arr);
Copy the code

To get the general idea straight:

  1. The default value is I = 1, so preIndex is the cursor of the internal loop.
  2. Current saves arR [I] and determines the final position of current through the loop;
  3. At the beginning of each inner loop, arr[I] === current === ARr [preIndex + 1], so there is no need to worry about the loss of arr[I] when arr[preIndex + 1] = arr[preIndex];
  4. General idea is that the need to position the elements extra cache first, and then to use inner loop, the need to adjust the elements of the assigned to it at the back of a position, form and in turn, finally because of inner loop in judging conditions take effect when not stop means of finding the right position, the need to position elements and then assignment, complete the sorting.

Series of links (will be updated later) :

  • The difference between bubble sort and selection sort