preface

When the order of data to be sorted is opposite to the expected sorting result, the sorting efficiency is the worst. The half-insert sort we talked about last time only reduces the comparison times of ordered lists, and the number of traversal times of the overall data is still not optimized; The next hill sort is to optimize the overall data so as to improve the sorting efficiency.

The body of the

1.1 Idea of Hill sorting algorithm

** Shell’s Sort is an improved version of direct insert Sort, also known as “Diminishing Increment Sort”.

Algorithm thought

The data to be sorted are grouped according to the specified step size and sorted by direct insertion. The step size is reduced, grouping is repeated, and insertion sort is repeated directly until the last insertion sort is carried out when the step size is 1.

The first step size can be customized as required, but the recommended value is the number of elements divided by 2(Lenght /2), and the subsequent step size is the previous step divided by 2(stepk=stepk-1/2) until the step size is 1, as shown below:

Step size can be understood as increments, and the process of reducing step size, which is also called shrinking increments, is hill sort, also known as shrinking increment sort.

Grouping principle (step1=6/2=3 for the first grouping) :

  • Group 1: the index bit of 0 is 2, the index bit of 0+step1 is 3, and the corresponding element is 1, 3+step1 crosses the boundary, so the elements of group 1 are 2 and 1;
  • Group 2: the index bit of 1 is 5, the index bit of 1+step1 is 4, the corresponding element is 9, 4+step1 crosses the boundary, then the elements of group 2 are 5 and 9;
  • Group 3: the index bit of 2 is 6, the index bit of 2+step1 is 5, and the corresponding element is 3, 5+step1 crosses the boundary, so the elements of group 3 are 6 and 3; The elements are now grouped;

The next group will successively decrease the step size, that is, the last step size divided by 2 is rounded; Then continue to group the results of the last sorting according to the newly calculated step size; Until the step size decreases to 1, the whole whole conducts the last direct insertion sort;

1.2 Hill sorting algorithm implementation and analysis

Code implementation (ascending) :

The running results are as follows:

Step analysis:

Above steps:

  • Copy the original data array to arrayB in the new array. The main purpose of this step is not to declare additional temporary variables later, but also to achieve simple logic for the subsequent core code and reduce excessive judgment. The 0 index bit also acts as a sentinel;
  • The first step is to calculate the first step size step1=3 according to the number of elements. According to the step size, the data to be sorted are grouped into virtual groups. The element with index bit 1 and the element with index bit 1+step are grouped into a group, the element with index bit 2 and the element with index bit 2+step are grouped into a group, and the element with index bit 3 is grouped into a group. Then, the data to be sorted are divided into 2 and 1. 5, 9; 6, 3 groups;
  • The second step starts to traverse each group of data and conducts direct insertion sort for each group of data; First of all, the first group of data 2 and 1, put the data 1 to be sorted into the sentry position (i.e., index bit 0), and compare the sentry position 1 with 2 in the ordered list. If 2 is larger than 1, the space needs to be vacated, so 2 is moved to the position with index bit 4 in the group. Then insert the sentry data 1 into the vacated space;
  • The third step traverses the second set of data 5 and 9. First, put the data 9 to be sorted into the sentry position (i.e., index bit 0), compare the sentry data 9 with 5 in the ordered list. If 5 is less than 9, the position does not need to be changed.
  • The fourth step traverses the third group of data 6 and 3. First, put data 3 to be sorted into sentry position (i.e. index position 0). Compare data 3 of sentry position with 6 in the ordered list. Then insert sentry data 3 into the vacated space;
  • After the grouping sorting is completed, the first grouping sorting result is finally obtained:

After the sorting of the first grouping is completed, adjust the step size and continue the grouping. Since the step size calculated in the second time is step2=step1/2=1, it is ok to insert the sorting of all the data in the last grouping into one group directly for the last time; Here will not repeat the demonstration, specific steps and before said to direct insertion sort, referring to the leader of this article alone to talk to me two sentences: do not forget the algorithm framework at the same time.

After the second insertion sort is done, we get the final sort.

1.3 Analysis of Hill sorting algorithm

Time complexity

The time complexity of hill sort is O(n(1.3~2)), which is better than O(n2). The time complexity of Hill sort is O(n(1.3~2)).

In the core part of the algorithm, only a few fixed intermediate variables ((I,j,step, arrayB [0])) are used for spatial complexity. Therefore, the memory consumed during the algorithm is a constant, so the spatial complexity is O(1).

Stability Because the original data is grouped according to the step size in the sorting process, the same elements may be divided into different groups, and the order of the original two same elements cannot be guaranteed in the final sorting, so the Hill sorting is unstable.

To sum up, Hill sort is an unstable algorithm whose time complexity is O(n2) and space complexity is O(1).

conclusion

Now that I’ve done three kinds of insertion sort, I’ll do swap sort in the next video; The key points about insert sort are summarized here (in green). As follows:

Thank you for your likes, favorites and comments. Continue next time **~~ **

A handsome guy who was made ugly by the program, pay attention to “Code variety circle “, learn with me ~~~