How to implement Hill sort algorithm in Python

Algorithm Description

Hill sorting, also known as "shrinking incremental sorting", is a sorting algorithm produced by optimizing insertion sort. Its execution idea is: group the elements in the array into subscript increments, insert and sort each group of elements, reduce the increment and repeat the previous steps until the increment reaches 1.

Generally speaking, the time complexity of Hill sorting is O(n1.3)~O(n2), which depends on the increment size. The space complexity of Hill sorting is O(1), which is an unstable sorting algorithm. When performing Hill sorting, one move of an element may span multiple elements, which may offset multiple moves and improve efficiency.

The following is an ascending Hill sort using (array length/2) as the initial increment. After each round of sorting, the increment is reduced by half.

Step one:

As shown in Figure 2-28, starting from the first element, group by increment 4. It can be seen that when the increment is 4, there are only two elements in a group, otherwise the subscript of the element will exceed the range of the array.

Step 2:

As shown in Figure 2-29, insert and sort the elements in the group.

The third step:

As shown in Figure 2-30, continue to use the same method to group, insert and sort the elements in the group so that they Orderly.

After all the numbers in the entire array have been traversed, this round of sorting is over. Reduce the increment by half and continue with the next round of sorting.

Step 4:

As shown in Figure 2-31, when the increment is 2, it can be seen that the elements in each group have increased and the total number of groups has decreased. Continue insertion sorting the elements in each group until each group is traversed.

The fifth step:

The final round of sorting is shown in Figure 2-32, and the increment is reduced by half again; at this time the increment is 1 , which is equivalent to performing insertion sort on the entire array, which is the final round of sorting.

After the last round of sorting, the entire Hill sorting is over.

Code implementation

In the for loop, since the first element of each group does not need to be inserted and sorted, and their subscripts are between 0 and step-1, so start from the subscript step Traverse.

It should be noted that if you want to simulate the approach in the flow chart, you need to use two loops: first group, and then order the elements in the same group at once. In order to improve efficiency, we directly use a for loop. Every time a number is traversed, the group in which it is located is inserted and sorted. This traversal also meets the order requirements of insertion sort. In insertion sort, the value of the current subscript needs to be changed, so the variable ind is used to store the current subscript to prevent it from affecting the for loop.

Ordinary insertion sort is equivalent to Hill sorting with an increment of 1. Hill sorting across elements actually only changes the increment, and is logically no different from ordinary insertion sorting.

Hill sorting code:

nums = [5,3,6,4,1,2,8,7]
def ShellSort(nums):
  step = len(nums)//2　　　　　　　　 #初始化增量为数组长度的一半
  while step > 0:　　　　　　　　　　 #增量必须是大于0的整数
   for i in range(step,len(nums)):　#遍历需要进行插入排序的数
     ind = i
     while ind >= step and nums[ind] < nums[ind-step]: #对每组进行插入排序
      nums[ind],nums[ind-step] = nums[ind-step],nums[ind]
      ind -= step
   step //= 2　　　　　　　　　　　#增量缩小一半
  print(nums)
ShellSort(nums)

Run the program, the output result is:

[1,2,3,4,5,6,7,8]

The above is the detailed content of How to implement Hill sort algorithm in Python. For more information, please follow other related articles on the PHP Chinese website!