shell sort Algorithm
Shell sort, also known as Diminishing Increment Sort, is an efficient in-place comparison based sorting algorithm that is an extension of the insertion sort. It was invented by Donald L. Shell in 1959. The algorithm works by first arranging elements at a specific interval apart, forming a sub-array, and then sorting these sub-arrays using an insertion sort. After sorting the sub-arrays, the interval is reduced, and the process is repeated until the interval becomes one, making it a standard insertion sort. The advantage of shell sort over traditional insertion sort is that it can move elements to their correct positions much faster, as it takes advantage of the partially sorted sub-arrays.
The performance of the shell sort algorithm largely depends on the choice of the interval sequence. The original shell sort algorithm used intervals of powers of two minus one, but further research has led to the discovery of more efficient interval sequences, such as the Pratt sequence, the Hibbard sequence, and the Sedgewick sequence. By choosing a good interval sequence, the shell sort algorithm can achieve a time complexity of O(n^(3/2)) or even O(n*log(n)), making it suitable for sorting medium-sized arrays. While it may not be as efficient as more advanced sorting algorithms like merge sort or quick sort, shell sort is relatively easy to implement and requires less overhead, making it a popular choice for certain applications.
"""
This is a pure Python implementation of the shell sort algorithm
For doctests run following command:
python -m doctest -v shell_sort.py
or
python3 -m doctest -v shell_sort.py
For manual testing run:
python shell_sort.py
"""
def shell_sort(collection):
"""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]
for gap in gaps:
for i in range(gap, len(collection)):
j = i
while j >= gap and collection[j] < collection[j - gap]:
collection[j], collection[j - gap] = collection[j - gap], collection[j]
j -= gap
return collection
if __name__ == "__main__":
user_input = input("Enter numbers separated by a comma:\n").strip()
unsorted = [int(item) for item in user_input.split(",")]
print(shell_sort(unsorted))
