————— the next day —————
— — — — — —
Let’s review insertion sort first:
Insert sort, as the name implies, is in the sorting process, each element in the array according to the size of the relationship, the corresponding position of the ordered region.
For example, element 3 in the following array needs to be inserted before the first three elements of the ordered region, and the first three elements need to be moved back accordingly:
The result of each round is as follows: insert sort (array length -1)
The average time complexity of insertion sort is O (n^2). This sorting algorithm is not complicated, but it is obviously not an efficient sorting algorithm.
So, how can you optimize the insertion sort algorithm? Let’s start with two features of insert sort:
1. In the case that most elements are already in order, insertion sort requires less work
It is obvious from this conclusion that if most elements in an array are ordered, then the elements in the array do not need to be compared and swapped frequently.
2. When the number of elements is small, the workload of insertion sort is small
The result is even more obvious: the amount of work done by insertion sort is proportional to the square of n, and if n is small, the amount of work done by insertion sort is much smaller.
How do you preprocess the raw array? Clever scientists came up with a way of grouping and sorting, in order to make some “rough adjustments” to the array.
Grouping means that the elements are grouped in pairs, and the span between the two elements in the same group is half of the total length of the array, so the span is 4.
As shown in the figure, element 5 is grouped with element 9, element 8 is grouped with element 2, element 6 is grouped with element 1, element 3 is grouped with element 7, altogether 4 groups.
Next, we have each set of elements sorted independently, using a direct insert sort. Because each group has a small number of elements, only two, insertion sort is a small amount of work. Each sorted array looks like this:
In this way, after just a few simple swaps, the overall order of the array is significantly improved, so that the subsequent direct insert sort work is greatly reduced. This can be interpreted as a “rough tweak” to the original array.
But this is not the end, we can further narrow the group span, repeat the above work. Regroup the elements by reducing the span by half, that is, by 2:
As shown in the figure, there are two groups of elements 5,1,9,6 and 2,3,8,7.
Next, we continue to sort each group of elements independently, using direct insert sort. Each sorted array looks like this:
At this point, the array is further ordered, paving the way for subsequent sorting.
Finally, we reduced the grouping span even further, to one, which is the same thing as doing direct insertion sort. After a series of rough adjustments, the amount of work of direct insert sort has been reduced, and the result is as follows:
Let’s go through the whole grouping sorting process again:
The idea of piece-by-group rough tuning like this, followed by direct insertion sort, is hill sort, named after its inventor, computer scientist Donald Shell.
The grouping span (4,2,1) used in the above example is known as the increments of hill sort. There are many options for increments. The incremental method we used in the example is a naive method proposed by Donald Shell when he invented hill sort, which is called hill increments.
Public static void sort(int [] array){// int d=array.length;while(d>1) {// Use hill increments, i.e., half d=d/2;for(int x=0; x<d; x++) {for(int i=x+d; i<array.length; i=i+d) { int temp=array[i]; int j;for(j=i-d; j>=0&&array[j]>temp; j=j-d) { array[j+d]=array[j]; } array[j+d]=temp; }}}} public static void main (String [] args) {int [] array = {5,3,9,12,6,1,7,2,4,11,8,10}; sort(array); System.out.println(Arrays.toString(array)); }Copy the code
If we look at the array above, if we do the same grouping as we did before, whether it’s in increments of 4 or 2, there’s no swapping of elements inside each group. Until we reduce the increment to one, the array will be adjusted to insert sort.
For such arrays, hill sort increases the cost of grouping rather than reducing the amount of direct insertion sort.
How do you choose a more efficient incremental method for Hill sorting?
To ensure that there are no blind spots in grouping rough tuning, the increments of each round need to be “quality” to each other, that is, there is no common divisor other than 1.
Therefore, many kinds of increment methods have been proposed, among which Hibbard increment and Sedgewick increment are the most representative ones.
Hibbard’s delta sequence is as follows:
1，3，7，15……
The general term is 2 to the k minus 1
With this incremental Hill sort, the worst time complexity is O (n^(3/2)).
Sedgewick’s delta sequence is as follows:
1, 5, 19, 41, 109……
The general formula is 9 times 4 to the k minus 9 times 2 to the k plus 1 or 4 to the K minus 3 times 2 to the k plus 1
With this incremental hill sort, the worst time complexity is O (n^(4/3)).
As for the time complexity of these two increments, some of them require very complicated mathematical proofs, and some of them are rough guesses, so you don’t have to worry about them for the moment.
In the array above, there are two elements 5, the green 5 is first and the orange 5 is last.
If we group by Hill increments, after the first round of rough tuning (increments of 4), the green element 5 will be swapped with the orange element 5:
After the second round of rough adjustment (increment of 2) :
Final sorting result:
The same element, 5, changes its order after sorting, so it can be seen that Hill sort is an unstable sort.
— — the END — — –
Like this article friends, welcome to pay attention to the public number programmer xiao Grey, watch more exciting content
Welcome to long click on the QR code to follow Xiao Grey learning English, you learn more than English!
