FilesExpand file tree

 Write-for-current-Python

/

shell_sort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

40 lines (33 loc) · 1.11 KB

 Write-for-current-Python

/

shell_sort.py

Copy path

Top

File metadata and controls

• Code
• Blame

40 lines (33 loc) · 1.11 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

"""

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

"""

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)):

insert_value = collection[i]

j = i

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

collection[j] = collection[j - gap]

j -= gap

if j != i:

collection[j] = insert_value

return collection

if __name__ == "__main__":

from doctest import testmod

testmod()

user_input = input("Enter numbers separated by a comma:\n").strip()

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

print(shell_sort(unsorted))