Easy to understand data structure and algorithm series (Hill Sort)

preface

A new series, “Easy to Understand Data Structures and Algorithms by Looking at Pictures”, is launched, mainly using pictures to describe common data structures and algorithms, easy to read and understand. This series includes dozens of examples of heaps, queues, lists, trees, graphs, sorts, and more.

Hill sorting

Hill sort is a kind of sorting method proposed by Hill (Donald Shell), also belongs to insertion sort, but the efficient version of simple insertion sort, also known as reduced increment sort. The basic idea is to incrementally group the elements to be sorted, and then insert sort within the grouping group. As the increment decreases, there are more and more elements in each grouping group until the increment decreases to 1, and all elements are assigned to the same group. After insertion sort is performed, the whole sorting operation is completed.

Ranking points

Pick an integer less than the number of elements to be sorted, nAs the first increment, all elements are grouped based on all distances ofMultiples of the records were divided into the same group.
For the sorted groups, direct insertion sort is performed within the groups.
And then we take the second change, including<, then continue grouping according to the new increment and do a direct insert sort within the group.
Repeat step 3 until the increment is equal to 1, that is, all records are in the same group, then perform direct insert sort to complete the sort.

Hill sort can take half of the number of elements in the first increment and then cut it in half each time until the increment is 1.

Sorting process

Suppose we have the following seven elements, 84, 25, 59, 71, 62, 16, 34, and now do Hill sort.

The first round takes half of the number of elements as increments, that is, 7/2, and takes 3, so the first round increments by 3, and then the first group is the element with index 0,3, and 6, that is, 84,71,34.

Taking 84 as the sorted sequence, and then preparing to insert the second element 71 into the sorted sequence,

71 is less than 84, so 84 moves back to where 71 was,

The third element, 34, is then inserted into the sorted sequence, first compared with 84,

34 is less than 84, so 84 moves back, and then continues to compare to 71,

34 is less than 71, so 71 goes back, 34 goes in. Then I’m going to do the second group, which is the element with index 1,4, that’s 25,62, insert sort,

Taking 25 as the sorted sequence, and inserting the second element 62 into the sorted sequence,

25 is less than 62, so it’s not moving. And then I’m going to do the third group, and the third group is the element with index 2,5, 59,16, insert sort,

Take 59 as the sorted sequence and insert the second element of the group, 16, into the sorted sequence.

16 is less than 59, so 59 moves back and 16 moves forward. At this point, the increment is 3.

The increment in the second round is 1/2 of the increment in the last round, that is, 3/2, so the increment in the second round is 1. At this time, all elements form the same group. Insert sort operation on this group, first, regard 34 as the sorted sequence, and prepare to insert 25 into the sorted sequence.