The rotting…

Insert sort works by selecting the element at the current index I and searching from right to left for the correct place to place the item.

Implement insert sort

Insertion sort is a very simple algorithm that works best for most data that has already been sorted. Before you start, it’s a good idea to visually demonstrate how the algorithm works. You can refer to the previous animation to see how insert sort works.

The basic idea of the algorithm is to select one element at a time, then search and insert it into the correct position. Hence the name: Insert sort. This operation will cause the array to be split into two parts — the sorted part and the unsorted elements. Some people like to picture it as two different arrays — one containing all the unsorted elements and the other having all the sorted elements. But describing it as an array is more consistent with how the code works.

Let’s look at the code first, and then discuss it.

const insertionSort = (nums) = > {
  for (let i = 1; i < nums.length; i++) {
    let j = i - 1
    let tmp = nums[i]
    while (j >= 0 && nums[j] > tmp) {
      nums[j + 1] = nums[j]
      j--
    }
    nums[j+1] = tmp
  }
  return nums
}
Copy the code

There are two indexes in the insert sort code: I and j. I is used to track the outer loop and represent the current element being sorted. It starts at 1 instead of 0, because when we only have one element in a newly sorted array, there’s nothing to do. So start with the second element and compare it to the first. The second index j starts at i-1 and iterates from right to left until it finds the correct place to place the element. In this process, we move each element back one place to make room for the new elements to be sorted.

That’s all it takes! If you’re only interested in the implementation, you don’t have to look any further. But if you want to know how to implement this algorithm correctly, keep reading!

Check the loop invariant condition

To determine whether the algorithm works properly rather than just producing the correct output for a given input, we can establish a set of conditions that must be true at the beginning of the algorithm, and at the end of the algorithm, each step of the algorithm is in the condition. This set of conditions is called loop invariants and must remain true after each iteration of the loop.

Cyclic invariants are not always the same thing. It all depends on the implementation of the algorithm, something we as algorithm designers must determine. In our example, we iterate over one element in the array at a time, then search from right to left for the correct place to insert it. This will result in the left half of the array (up to the current index) always being the sorted arrangement of the elements originally found in the array slice. Or another way to say it is

The cyclic invariant of insertion sort represents the order in which all elements to the current index “A [0..index]” constitute the elements originally found in “A [0..index]” before we started sorting.

To check these conditions, we need a function that can be called in the loop and receives as an argument:

  1. Newly sorted array
  2. Original input
  3. The current index.

Once we have this, we can slice the array from 0 to the current index and run our check. The first check is that all the elements in the new array are contained in the old array, and the second check is that they are all ordered.

// Check the insertion sort loop invariant function
const checkLoopInvariant = (newArr, originalArr, index) = > {
  //need to slice at least 1 element out
  if (index < 1) index = 1

  newArr = newArr.slice(0,index)
  originalArr = originalArr.slice(0, index)

  for (let i=0; i < newArr.length; i++) {

    //check that the original array contains the value
    if(! originalArr.includes(newArr[i])) {console.error(`Failed! Original array does not include ${newArr[i]}`)}//check that the new array is in sorted order
    if (i < newArr.length - 1 && newArr[i] > newArr[i+1]) {
      console.error(`Failed! ${newArr[i]} is not less than ${newArr[i+1]}`)}}}Copy the code

If this function is called before, during, and after the loop, and it passes without any errors, we can confirm that our algorithm is working properly. Modify our code to include this check, as follows:

const insertionSort = (nums) = > {
  checkLoopInvariant(nums, input, 0)
  for (let i = 1; i < nums.length; i++) {
    ...
    checkLoopInvariant(nums, input, i)
    while (j >= 0 && nums[j] > tmp) {
      ...
    }
    nums[j+1] = tmp
  }
  checkLoopInvariant(nums, input, nums.length)
  return nums
}
Copy the code

Note the state of the array after index 2 in the figure below, which has sorted the three elements.

As you can see, we have processed three elements, the first three in order. You can also see that the first three digits in the sorted array are the same as the first three digits in the original input, just in a different order. So we keep the loop invariant.

Analysis run time

The last thing we’ll look at using insert sort is the runtime. Performing real runtime analysis requires a lot of math, and you can quickly find your own weeds. If you are interested in such analysis, see Cormen’s Introduction to Algorithms, 3rd edition. However, for the purposes of this article, we will only do the worst-case analysis.

The worst case of insert sort is when the input array is sorted in reverse order. This means that we need to iterate over each element and find the correct insertion point in the already sorted element. The outer loop represents the total number of times from 2 to n (where n is the size of the input), and each iteration must perform i-1 operations because it iterates from i-1 to zero.

The proof of this conclusion is beyond the scope of this paper. To be honest, I’m just comparing it to the best case, where the elements are already sorted so that the time required for each iteration is fixed……

In terms of big-o notation, the worst-case is Ɵ(n²) and the best-case is Ɵ(n). We always take the worst case, so the complexity of the whole algorithm is Ɵ(n ^ 2).

conclusion

Insertion sort works best when the input array is already largely sorted. A good program is to insert a new element into an already sorted datastore. Even though you may never have to write your own sorting algorithm, and other types (such as merge sort and quicksort) are faster, I think it’s fun to analyze algorithms this way.

Welcome to pay attention to the front-end public number: front-end pioneer, access to front-end engineering practical toolkit.