Shell Sort

Last time, there were three basic sorts: bubble sort, selection sort, and insertion sort.

Insertion sort is also called direct insertion sort, whose core idea is to select the first data from the unsorted sequence by constructing ordered sequence, scan the sorted sequence from back to front, find the corresponding position and insert. Direct insertion sort is very efficient for small or basically ordered data.

Hill sorting, invented by Donald Shell in 1959, was the first breakthrough O(n²) sorting algorithm. Hill sort is an improved version of direct insert sort (why don’t I write direct insert sort together? Bloggers are so stupid that It took Hill two days to understand the loopy –).

Hill sort divides the sequence into several small sequences (logically grouped), and inserts and sorts each small sequence. At this time, each small sequence has a small amount of data, and the efficiency of inserts and sorts is also improved.

Algorithm description

  • Select an incremental sequence, T1, T2…. Tk, where Ti >tj, tk = 1;
  • Sort the sequence k times according to the number of incremental sequences k;
  • In each sorting, the sequence to be sorted is divided into several sub-sequences according to the increment TI, and the sub-sequences are sorted by direct insertion respectively. When the increment is tk, which is 1, the last sort is done, and the subsequence is the sort sequence itself.

Dynamic graph demonstration

(d) this map is too abstract, need to read more than 12345678 times.

Code implementation

Let’s take a look at another blog graphic:

The graph is grouped according to subscript distance 4, arr[0] and ARR [4] are a group, arr[1] and ARr [5] are a group, where subscript distance 4 is called incremental.

After insertion sort of the four subsequences:

At this point, all four subsequences are ordered, and the array becomes:

Then reduce the increment to half of the last increment :2, continue to divide groups, at this time, the number of elements in each group is larger, but the array changed part is ordered, the insertion sort efficiency is also relatively high

Set the increment to half of the previous increment: 1, and the array is divided into groups. At this point, the array is nearly ordered:

If this doesn’t make sense to you… Then you are as stupid as I am. Just keep reading 12345678.

    let arr = [3.45.16.8.65.15.36.22.19.1.96.12.56.12.45];
    let len = arr.length;
    let willInsertValue; 
    let gap = len; // Define the increment
    // Dynamically define the sequence of increments, each increment is half of the last increment, and the gap of the last increment is 1
    while(gap>0&&(gap = Math.trunc(gap/2))) {// Insert sort for each group, why I starts with gap, because the default insert sort is the first sorted sequence, and arr[gap] is the first group second
        for(leti = gap; i<len; i++){// Insert a[I]
            willInsertValue = arr[i];
            // Insert by group, this is a bit tricky. As mentioned earlier, it is just a logical grouping, but it is actually a sequence. Insert by group is crossed
            // Insert
            let j = i - gap;
            // The following is a direct insertion sort, but each time the subscript difference is gap
            while(j>=0&&arr[j]>willInsertValue){
                arr[j+gap] = arr[j];
                j -= gap
            }
            arr[j+gap] = willInsertValue
        }
    }

Copy the code

The output is:

Analyze the complexity:

The space complexity is still order one.

The execution time of Shell sort depends on the incremental sequence.

Common characteristics of good incremental sequences:

  • The last increment must be 1;
  • Values in a sequence (especially adjacent values) should be avoided as much as possible.

In this case, the 1,2,4 increments chosen above are not very good, and the worst time complexity of using such increments is O(n squared).

Hibbard proposed another delta sequence {1,3,7… ,2^k-1}, the time complexity of such a sequence (worst case) is O(n^1.5).

Sedgewick proposed several incremental sequences with a worst-case running time of O (n^1.3), of which the best sequence is {1,5,19,41,109,… }

It doesn’t matter which increment is used for the result, as long as the last increment is 1. The above chestnut increment cannot be greater than the length of the sequence to be sorted, otherwise the gap is 0 and sorting cannot be carried out.

Hill sort is also called reduced increment sort.

And finally, stability, because Hill sort is cross jump sort, it’s unstable sort.

conclusion

Personally, when learning Hill sort, the difficulty lies in the final cross jump insertion sort. As mentioned before, it is grouping logically, and thinking is completely restricted by grouping. When always thinking about sorting, it is also sorting by group.

Applicable scenario

Hill sort is an optimization of direct insert sort and can be used for large arrays. Hill sort is much faster than insert sort and selection sort, and the larger the array, the greater the advantage.

reference

  • Top ten classic front-end algorithms

  • Hill ordering – easy to understand diagram

  • Hill sort – Baidu Encyclopedia

Next up

【 Small front End 】 Front end sorting algorithm phase 3 (not simple selection sort – heap sort)