shell_sort.py

"""
https://en.wikipedia.org/wiki/Shellsort#Pseudocode
"""


defshell_sort(collection: list[int]) ->list[int]:
"""Pure implementation of shell sort algorithm in Python
 :param collection: Some mutable ordered collection with heterogeneous
 comparable items inside
 :return: the same collection ordered by ascending

 >>> shell_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> shell_sort([])
 []
 >>> shell_sort([-2, -5, -45])
 [-45, -5, -2]
 """
# Marcin Ciura's gap sequence

gaps= [701, 301, 132, 57, 23, 10, 4, 1]
forgapingaps:
foriinrange(gap, len(collection)):
insert_value=collection[i]
j=i
whilej>=gapandcollection[j-gap] >insert_value:
collection[j] =collection[j-gap]
j-=gap
ifj!=i:
collection[j] =insert_value
returncollection


if__name__=="__main__":
fromdoctestimporttestmod

testmod()
user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(shell_sort(unsorted))