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

Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort. Hill sort is an unstable sort algorithm. — Wikipedia

Hill sorting is a sorting algorithm proposed by D.L.Shell in 1959. Before this, the time complexity of sorting algorithms is basically O(n²). Hill sorting algorithm is one of the first algorithms to break through this event complexity.

The sorting method developed by Hill, a scientist, improves the efficiency of direct insertion sorting.

Algorithm to interpret

In the last section, we talked about direct insertion sort, which is very efficient when the array itself is basically ordered and the number of elements is small. The problem is, those two conditions are inherently tough. How do you make a program strive for these two conditions? The answer is to speak to group had a large number of elements of the array, divided into several sub array, so that each child the number of elements in the array to sort is less, and then separately within the subarray “direct insertion sort”, when the basic orderly array, again to all the elements on a “direct insertion sort”.

The so-called basic order means that the small elements are basically in the front, the large elements are basically in the back, and the medium and large elements are basically in the middle. Note that something like [2, 1, 3, 6, 4, 7, 5, 8, 9] is basically ordered, but something like [1, 5, 9, 3, 7, 8, 2, 4, 6] is not.

Therefore, we need to adopt the strategy of jump splitting when dividing the subarray: the records with a certain increment apart are grouped into a subarray, so as to ensure that the results obtained by direct insertion sort in the subarray are basically ordered, rather than locally ordered.

For example

This algorithm is ambiguous no matter how it is explained, so let’s go straight to the illustration above.

Assuming we now have an array of ARR: [8, 9, 1, 7, 2, 3, 5, 4, 6, 0], we set the initialization step to gap = arr.length/2 = 10/2, that is, 5. Split the subarray in increments of 5, treating each column as a subarray:

// Column 1 column 2 column 3 column 4 column 5 8 9 1 7 2 3 5 4 6 0Copy the code

Then perform class direct insertion sort for each column, and obtain:

// Column 1 column 2 column 3 column 4 column 5 3 5 1 6 0 8 9 4 7 2Copy the code

Then the order of the original array should be: [3, 5, 1, 6, 0, 8, 9, 4, 7, 2], and then narrow the increment, gap = 5/2 = 2, then the array is divided as follows:

Column 1 column 2 3 5 1 6 0 8 9 4 7 2Copy the code

Continue the direct insertion sort for each column, and obtain:

// Column 1 2 0 2 1 4 3 5 7 6 9 8Copy the code

Then the order of element group should be: [0, 2, 1, 4, 3, 5, 7, 6, 9, 8], which is basically ordered. At this time, the increment should be calculated as: gap = 2/2 = 1, then apply the array directly to insert sort, and finally get:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Copy the code

The specific implementation

var shell_sort = function(arr){
  var i, j, temp, gap;
  var len = arr.length;

  // Gradually shrink the increments
  for (gap=len>>1; gap>=1; gap>>=1) {
    // Class inserts the sorting algorithm directly
    for (i=gap; i<len; i++) {
      if (arr[i] < arr[i-gap]) {
        temp = arr[i];
        for (j=i-gap; j>=0 && temp<arr[j]; j-=gap) {
          // Find the insertion position
          arr[j+gap] = arr[j];
        }
        / / insertarr[j+gap] = temp; }}}return arr;
};

shell_sort([8.9.1.7.2.3.5.4.6.0]);
Copy the code

I don’t know if you have noticed, but the first loop inside the two nested loops, is actually “direct insertion sort”, the difference is that there is a variable gap, but actually when gap === 1, it is exactly the same as the algorithm we learned in the last video.

Summary of algorithm Implementation

Through the analysis of the above code, we can see that the key of Hill sort is not simply by 1 increment group sort, and then merge the whole sort; Instead, an initial increment is selected and the increment is continuously decrement, and a direct insertion sort is needed between each decrement, so that the sorting efficiency is improved.

In addition, any increment sequence will work as long as the final increment is 1, because eventually when the increment is 1, the algorithm changes to “direct insertion sort”, which guarantees that the data will be sorted.

Complexity analysis

Donald Shell initially suggested choosing a step size of n/2 and taking half the step size until it reached 1. Although this can be better than the O(n²) algorithm (insertion sort), there is still room to reduce the average and worst times. — Wikipedia

Consult Wikipedia and related articles to get the following conclusions:

  1. The original incremental sequence of Hill sort isn/(2^i), that is: n/2, n/4… , 1; The worst case time is zeroO (n squared)
  2. The incremental sequence proposed by Hibbard is2^k-1, namely: 1, 3, 7… , 2 ^ k – 1; The worst case time is zeroO(n^(3/2))
  3. The delta sequence proposed by Sedgewick is the best known delta sequence, namely: 1, 5, 19, 41, 109,…. ; The items of the item sequence come fromand

In summary, with the advent of Hill sorting algorithm, we finally broke through the era of slow sorting, that is, beyond the time complexity of O(n²). In the next few articles, we will introduce more efficient sorting algorithms.

Refer to the link

Zh.wikipedia.org/wiki/%E5%B8…

Faculty.simpson.edu/lydia.sinap…



If you think this article is good, share it with your friends