Interview essential algorithm | graphic Hill sorting (Python)

Shell Sort

Hill's idea of sequencing

​ Hill sort is an improved method of insertion sort , It divides the original list into countless sub lists , Then insert sort is performed on each sub list , The key to Hill sorting is to control the step size ( It can be seen as taking elements as sub lists every few elements ).

Graphic Hill sort

​ Given the following list :

 Insert picture description here

​ We use 2 As step size ( Take an element every two characters ), It can be divided into three sub lists as follows .

 Insert picture description here

​ With three sub lists , We insert and sort the three sub lists respectively

 Insert picture description here

​ According to the above figure, we can find that the combination results we obtained are not completely sorted successfully , Finally, we need to do an insert sort on the list .

 Insert picture description here

​ So our Hill sorting is complete .

The nature of Hill sort

  • Optimal time complexity : O ( n ) O(n) O(n)
  • Worst time complexity : O ( n 2 ) O(n^2) O(n2)
  • stability : unstable
  • Compare insert sort : By changing the increment, the time complexity will be optimized .

Hill sort code implementation

lst = list(map(int, input().split(',')))
def shell_sort(alist):
n = len(alist)
gap = n // 2
while gap > 0:
for i in range(gap, n):
j = i
while j >= gap:
if alist[j] < alist[j - gap]:
alist[j], alist[j - gap] = alist[j - gap], alist[j]
j -= gap
else:
break
gap //= 2
return alist
shell_sort(lst)
Please bring the original link to reprint ,thank
Similar articles