This is the fourth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Hill sorting

A fast sorting algorithm based on insertion sort. Simple insertion sort is slow for large ordinal arrays, because elements can only be moved bit by bit from one end of the array to the other. For example, if the smallest element of the primary key happens to be at the end of the array, it takes n-1 moves to move it to the right position.

Hill sort simply improves insertion sort, also known as reduced increment sort, for speed.

Hill sort is to sort the array into a certain number of groups, using the direct insertion sort algorithm to sort each group; As the number of elements decreases, each group contains more and more elements. When the number is reduced to 1, the entire array is grouped into one group, and the sorting is complete. This shrinking number, then, forms a sequence of increments, and these numbers are called increments.

Code implementation

public class ShellSort { public static final int[] ARRAY = {12, 9, 6, 11, 5, 1, 14, 2, 10, 4, 8, 7, 13, 3}; public static int[] sort(int[] array) { int len = array.length; if (len < 2) { return array; } // The current data to be sorted has been sorted int current; Int gap = len / 2; while (gap > 0) { for (int i = gap; i < len; i++) { current = array[i]; Int index = i-gap; while (index >= 0 && current < array[index]) { array[index + gap] = array[index]; // Index -= gap; } // Insert array[index + gap] = current; } // gap = gap / 2; } return array; } public static void print(int[] array) { for (int i : array) { System.out.print(i + " "); } System.out.println(""); } public static void main(String[] args) { print(ARRAY); System.out.println("============================================"); print(sort(ARRAY)); }}Copy the code

Time complexity

The complexity of Hill sorting is related to incremental sequences.

Under the previous large increment, the size of each subsequence is small, and the sorting efficiency with direct insertion is high. Although the subsequence is larger and larger in the subsequent increment decreasing, the sorting efficiency is still high because the ordering of the whole sequence is more and more obvious.

In theory, as long as an array is decrement and the last value is 1, it can be used as an incremental sequence. Is there a sequence of steps that requires relatively few comparisons and moves in the sorting process, and that the time complexity of the algorithm is asymptotically optimal regardless of the number of sequence records to be sorted? But right now, mathematically, there’s no way to prove that any particular sequence is the best.

Common incremental sequences:

  • The Hill increment sequence: {n/2, (n /2)/2,… , 1}, where N is the length of the original array, this is the most common sequence, but not the best
  • Hibbard sequence: {2k-1,… , 3, 1}
  • Sedgewick sequence: {… } 9 * 4i- 9 * 2i + 1, I = 0,1,2,3,4…

Algorithm stability

Due to multiple insertion sort, we know that an insertion sort is stable, will not change the relative order of the same elements, but in the process of different insertion sort, of the same element may move in their respective insertion sort, 5,2,2,1 arrays, ranking the first element for the first time 5, and the third element 2 exchange, the second element will exchange and a fourth element 1, 2 The relative order of the two in the original sequence is broken, so hill sort is an unstable sorting algorithm.