Algorithm Introduction

Algorithm description and Implementation

Firstly, the whole record sequence to be sorted is divided into several subsequences for direct insertion and sorting. The specific algorithm description is as follows:

• Select an incremental sequence t1, t2 , tk, where ti > TJ, tk=1;
• < 2 >. The sequence is sorted by the number k of incremental sequences;
• < 3 >. For each sorting, the sequence to be sorted is divided into several subsequences of m length according to the corresponding increment ti, and each subsequence is inserted and sorted directly. Only when the increment factor is 1, the whole sequence is treated as a table, and the table length is the length of the whole sequence.

Javascript code implementation:

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    console.time('Hill sort time:');
    while(gap < len/5) {          //Define interval sequence dynamically
        gap =gap*5+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/5)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    console.timeEnd('Hill sort time:');
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

Hill sorting diagram (picture source network):

JAVA:

public static void shellSort(int[] arr){
    int temp;
    for (int delta = arr.length/2; delta>=1; delta/=2){                              //Sort each increment once
        for (int i=delta; i<arr.length; i++){              
            for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ //Note that Delta and delta are everywhere
                temp = arr[j-delta];
                arr[j-delta] = arr[j];
                arr[j] = temp;
            }
        }//loop i
    }//loop delta
}

Implementation code 2:

public static void shellSort2(int[] arr){
    int delta = 1;
    while (delta < arr.length/3){//generate delta
        delta=delta*3+1;    // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
    }         
    int temp;
    for (; delta>=1; delta/=3){
        for (int i=delta; i<arr.length; i++){              
            for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){
                temp = arr[j-delta];
                arr[j-delta] = arr[j];
                arr[j] = temp;
            }
        }//loop i
    }//loop delta
}

Algorithm stability

We all know that insertion sorting is a stable algorithm. However, Shell sorting is a process of multiple inserts. In one insert, we can ensure that the order of the same elements will not be moved. However, in multiple inserts, the same elements are likely to be moved in different insert rounds, and the final stability is destroyed. Therefore, Shell sorting is not a stable algorithm.

Applicable scenario of algorithm

Although shell sorting is fast, it is insert sorting after all, and its magnitude is not up-to-date -- quick sorting O(n ㏒ n) fast. Shell sorting is not a good algorithm in front of a large amount of data. However, it can be used for small and medium-sized data.

• Best case: T(n) = O(nlog2 n)
• Worst case: T(n) = O(nlog2 n)
• Average: T(n) =O(nlog n)