iframe-proxy | Sunbelt Computer Software

History

54 lines (43 loc) · 1.35 KB

Raw

"""

This is a pure python implementation of the shell sort algorithm

For doctests run following command:

python -m doctest -v shell_sort.py

python3 -m doctest -v shell_sort.py

For manual testing run:

python shell_sort.py

"""

from __future__ import print_function

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:

i = gap

while i < len(collection):

temp = collection[i]

j = i

while j >= gap and collection[j - gap] > temp:

collection[j] = collection[j - gap]

j -= gap

collection[j] = temp

i += 1

return collection

if __name__ == '__main__':

try:

raw_input # Python 2

except NameError:

raw_input = input # Python 3

user_input = raw_input('Enter numbers separated by a comma:\n').strip()

unsorted = [int(item) for item in user_input.split(',')]

print(shell_sort(unsorted))

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

shell_sort.py

Latest commit

History

shell_sort.py

File metadata and controls