preface

Since many algorithm problems in LeetCode involve some basic data structures, in order to better understand the animation of some complex problems updated later, a new series —– “Illustrated Data Structures” is launched, mainly using animation to describe common data structures and algorithms. This series includes ten kinds, heap, queue, tree, and search set, graph and so on about dozens of articles.

Hill sorting

Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort. But Hill sort is an unstable sort algorithm.

Hill sort is an improved method based on the following two properties of insertion sort:

  • Insertion sort has high efficiency when it operates on almost ordered data, that is, it can achieve the efficiency of linear sort.
  • But insert sort is generally inefficient because it can only move data one bit at a time;

The basic idea of Hill sorting is that the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion sorting respectively. When the records in the whole sequence are “basically ordered”, the whole records are directly inserted in sequence.

Algorithm steps

  1. Select an incremental sequence T1, T2… , where Ti > tj, tk = 1;

  2. Sort the sequence k times according to the number of incremental sequences k;

  3. In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.

Source: github.com/hustcc/JS-S…

Algorithm demo

Sort animation process explanation

  1. First, select delta gap = 10/2, and narrow delta continues as gap = gap/2

  2. The initial increment is gap = 10/2 = 5, and the array is divided into five groups

  3. It is divided into [8, 3], [9, 5], [1, 4], [7, 6], [2, 0] by color.

  4. Use the insertion sort described in the previous section for each of the five separate groups

  5. It turns out that the relatively small elements in each of the five groups were all tuned to the front

  6. Narrow the increment gap = 5/2 = 2, the entire array is divided into 2 groups

  7. 【 3, 1, 0, 9, 7 】, 【 5, 6, 8, 4, 2 】

  8. Apply the insertion sort described in the previous section to the two separate groups

  9. The order of the entire array is obvious

  10. Gap = 2/2 = 1, the array is divided into one group

  11. 0, 2, 1, 4, 3, 5, 7, 6, 9, 0

  12. At this point, a simple tweak to the above array is all that is needed to sort the entire array without a lot of movement

Code implementation

In order to better let readers use their familiar programming language to understand animation, the author will post a variety of programming language reference code, code all from the Internet.

C++ code implementation

Java code implementation

Python code implementation

JavaScript code implementation

Github.com/MisterBooo/…

You can pay attention to the public number five minutes learning algorithm for more sorting content.