Hill sort is a sort algorithm proposed by Donald Shell in 1959. Hill sort is also an insertion sort, which is a more efficient version of simple insertion sort, also known as reduced incremental sort, and was one of the first algorithms to break out of O(n2).

Shell sort

Hill sort is to group the records by a certain increment of the index and sort each group by direct insertion sort algorithm. As the increments decrease, each group contains more and more keywords, and when the increments decrease to 1, the entire file is exactly grouped and the algorithm terminates.

Algorithm description

Firstly, the whole record sequence to be sorted is divided into several sub-sequences for direct insertion sorting. The specific algorithm is described as follows:

  • Select a delta sequence T1, T2… , where Ti >tj, tk=1;
  • Sort the sequence k times according to the number of incremental sequences k;
  • In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.

Dynamic graph demonstration

Description:

  • The original array is [8,9,1,7,2,3,5,4,6,0]
  • The initial increment is gap=length/2=5, that is, the entire array is divided into 5 groups, the same color is a group
  • Perform a direct insertion sort on each of the five groups, and you can see that the smaller elements are moved to the front
  • Iterate again to narrow the increment gap=5/2=2, and the array is divided into 2 groups, the same color is a group
  • The above two groups were then sorted by direct insertion
  • Recursively narrow the increment gap=2/2=1, at which point, the entire array is 1 group

Code implementation

function shellSort(arr) { varlen = arr.length; for(vargap = Math.floor(len / 2); gap > 0; Gap = math.floor (gap / 2)) {// Note: for(vari = gap; i < len; i++) { varj = i; varcurrent = arr[i]; while(j - gap >= 0 && current < arr[j - gap]) { arr[j] = arr[j - gap]; j = j - gap; } arr[j] = current; } } returnarr; }Copy the code

Relation between Hill sort and insertion sort

Hill sorting was conducted on the basis of the insertion sort, one improved algorithm hill sorting is a original sequence into several subsequences, once for each subsequence to the insertion sort, and according to different subsequence partition size, final subsequence to 1, then insert with the original insertion sort is the same, It’s just that the queue is much more orderly than it used to be.

So hill sorting is to the original sequence and some finishing, its become orderly, and we all know, for the insertion sort algorithm the O (N2) level, the more orderly sequence, it needs the less time, in some cases can even close to O (N), this is the hill for insertion sort.

DORA sister [ITI2018] front-end fishing technology group

Welcome everyone technical exchange push touch fish help all can – link

Series of links (will be updated later)

  • Figure out quicksort

  • Insertion Sort

  • The difference between bubble sort and selection sort