Hill ordination attribute
The time complexity of the direct insertion sort algorithm written in the previous part is O(n^2). If the time complexity of the sorting algorithm is lower than O(n^2), it must be “remote element exchange” to improve the order degree of this group of elements, and then the direct insertion sort can reduce the workload of exchange.
What can be done to reduce the workload of swapping? Hill sort solves this problem.
It is hoped that the whole sequence to be sorted can be preprocessed before the direct insertion sort of Hill sort, in order to reduce the switching times and reduce the consumption of time in the last step of direct insertion sort.
Assume the initial state of the array: 5,1,9,3,7,4,8,6,2
Then set the initial increment to gap = length / 2 = 9/2 = 4, which means that the distance between the two elements is 4 (separated by 3 elements), and they will also be divided into 4 groups, [5,7,2], [1,4], [9, 8], [3, 6].
Direct insert sort is performed on each of these five groups. As the code progresses, they are all interspersed with direct insert sort, as you will see in the video animation below.
When sorting the 4 groups, then gradually reduce the increment, gap = 4/2 = 2, indicating that the distance between the two elements to be compared and exchanged is 2, divided into two groups, sorting the two groups.
The last incremental reduced to 1, this is the pure direct insertion sort, because in front of pretreatment, makes the “adjust” roughly, the sequence when doing the last step direct insertion sort, if to be sorted clear orderly, is actually reduce the number of exchange, also actually reduce the time of consumption.
(In the process of animation, there was a mistake in the middle of an element exchange, has been fixed, when playing the middle part of the action will be a little rushed).
Video animation: Hill sort swap method
Algorithm animation video address
Code
Result
Initial state [9, 5, 1, 3, 7, 4, 8, 6, 2] 4 incremental exchange [8, 5, 1, 3, 7, 4, 9, 6, 2] exchange [8, 5, 1, 3, 2, 4, 9, 6, 7] exchange [2, 1, 8, 3, 5, 4, 9, 6, 7] 2 incremental exchange [2, 1, 5, 3, 8, 4, 9, 6, 7] exchange [2, 1, 5, 3, 8, 4, 7, 6, 9] exchange [2, 1, 5, 3, 7, 4, 8, 6, 9] 1 incremental exchange [1, 2, 5, 3, 7, 4, 8, 6, 9] exchange [1, 2, 3, 5, 7, 4, 8, 6, 9] exchange [1, 2, 3, 5, 4, 7, 8, 6, 9] exchange [1, 2, 3, 4, 5, 7, 8, 6, 9] exchange [1, 2, 3, 4, 5, 7, 6, 8, 9] exchange [1, 2, 3, 4, 5, 6, 7, 8, 9]
In order to reduce the number of exchanges, we can also continue to optimize and adopt the moving method to reduce the time consumption of exchanges.
Video animation: Hill sort move method
Algorithm animation video address
Code
Result
Initial state [9, 5, 1, 3, 7, 4, 8, 6, 2] 4 incremental mobile [9, 5, 1, 3, 7, 4, 9, 6, 2] mobile [8, 5, 1, 3, 7, 4, 9, 6, 7] mobile [8, 5, 1, 3, 5, 4, 9, 6, 7] 2 incremental movement (2, 1, 8, 3, 8, 4, 9, 6, 7] mobile [2, 1, 5, 3, 8, 4, 9, 6, 9] mobile [2, 1, 5, 3, 8, 4, 8, 6, 9] 1 incremental movement [2, 2, 5, 3, 7, 4, 8, 6, 9] mobile [1, 2, 5, 5, 7, 4, 8, 6, 9] mobile [1, 2, 3, 5, 7, 7, 8, 6, 9] mobile [1, 2, 3, 5, 5, 7, 8, 6, 9] mobile [1, 2, 3, 4, 5, 7, 8, 8, 9] move [1, 2, 3, 4, 5, 7, 7, 8, 9]
Hill delta (Shell delta sequence)
The {4,2,1} used in the above procedure is known as hill sort increments and is the process of gradually reducing increments by half. The recursion formula of Shell delta sequence is:
The worst time complexity of Shell incremental sequences is O(n^2).
There are many kinds of selection of incremental sequence of Hill sort, and the selection proof and process of those incremental sequences are more complicated, so it is not tangled. This article presents two examples that are probably better than Shell delta sequences: Hibbard delta sequences and Sedgewick delta sequences.
Hibbard delta sequence
The general formula of Hibbard delta sequence is:
The recursive formula of Hibbard increment sequence is:
The worst time complexity of Hibbard delta sequence is O(n^(3/2)). The average time complexity is about O(n^(5/4)).
Code
What you get is the maximum initial increment that is less than length. Then, in the following code, modify only one step to get the initial increment, which is reduced in the same way as the Hill increment.
Sedgewick delta sequence
The general formula of Sedgewick delta sequence is:
The worst time complexity of Sedgewick delta sequence is O(n^(4/3)). The average time complexity is about O(n^(7/6)).
When you look at this formula for the first time, you don’t understand it. It turns out that there is also a small comma in the middle, which means that the set of the two delta sequences is searched, and the maximum value (initial delta) is smaller than length.
Code
It’s a little bit complicated, because there are two formulas, so you can’t just get the initial increment, and you have to figure out which formula to use to reduce the increment. Take the way to create a dynamic array in while(increment
For example, 9<<1 is converted to binary and shifted to the left by a few bits. For example, 9<<1 is converted to binary 1001 and then shifted to the left by one bit, followed by 10010. In decimal, this is 18.
For example, if 7<<2, 7 is converted to binary 111, which is 11100 when shifted two places to the left, and 32 when translated to decimal, which is equivalent to 7*(2^2)=32.
The “>>” operator is the same as dividing by two to the power.
The code below that gets the initial increment is also changed, and the increment reduction method is changed accordingly, and the rest of the code remains the same.
This paper introduces the basic idea, optimization and code implementation of Hill sort, including the choice of the last two incremental sequences. The selection of additional sequence is also very important to hill sort, which directly affects the performance of Hill sort.
Like this article friends, wechat search “algorithm clear strategy” public number, watch more wonderful algorithm animation articles