preface

Although the front-end interview will rarely test algorithm topics, but you will know when you go to the big factory interview, the master of the basic algorithm for computer science and technology for us, or essential, spend 10 minutes every day to understand the basic algorithm concepts and front-end implementation.

In addition, master some basic algorithm implementation, for our daily development, is also like a tiger added wings, can let our JS business logic more efficient and smooth.

Algorithm is introduced

We should have played poker, during the game players are basically touch cards and deal with cards, will put the card face value of the small card on the left, the card face value of the large card on the right, in ascending order (of course, there are also like descending order of the player). During the process, we are used to looking at the face value of the cards from left to right, comparing them in pairs, pulling out the cards and inserting them into a reasonable position. The way we deal with cards here is the “direct insertion sorting method”.

The basic operation of direct insert sort is to insert an element into an already sorted array, resulting in a new array with incremented Unicode values.

Algorithm diagram:

Implementation guidelines: Assume that arR has n elements, because the comparison, at least two elements, will be n-1 round. Each round of the loop compares elements with subscripts i-1 and I (1 <= I <= arr.Length-1). If the latter element has a larger Unicode value, the latter element is first stored in a variable called the “sentry variable.” And then we go into the subloop. Starting with the element with subscript i-1, each wheel cycle compares the Unicode value of the current element with the Sentry variable. If the current element is larger, the current element is assigned to the next element (the element with subscript + 1). The next wheel cycle continues until the current element is no larger than the Sentry variable. Exit the subloop and proceed to the next loop.

The specific implementation

var insertSort = function(arr){
  var i, j, m, mCnt=0;
  var len = arr.length;

  for (i=1; i<len; i++) {
    if (arr[i] < arr[i- 1]) {
      // Save the smaller element
      m = arr[i];
      for (j=i- 1; arr[j]>m; j--) {
        / / in the future
        arr[j+1] = arr[j];
        mCnt++;
      }
      console.log('Moved'+mCnt+'time');
      mCnt = 0;
      // Insert directly
      arr[j+1] = m; }}return arr;
};

insertSort([5.4.3.2.1]);
insertSort([3.2.1.7.8.9.0]);
Copy the code

Complexity analysis

In the best case, that is, the array passed in is already ordered, such as [1, 2, 3, 4, 5], then the number of comparisons is 5-1=4. Since it is already ordered, there are no moves, and the time complexity is O(n).

When the worst case is that the array passed is completely in reverse order, such as [5, 4, 3, 2, 1], then the comparison needs to be done as follows:

The number of moves will be as follows:

So the time complexity is still O(n ^ 2).