FilesExpand file tree

 master

/

shell_sort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

49 lines (38 loc) · 1.21 KB

 master

/

shell_sort.py

Copy path

Top

File metadata and controls

• Code
• Blame

49 lines (38 loc) · 1.21 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

41

42

43

44

45

46

47

48

49

"""

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:

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__":

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

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

print(shell_sort(unsorted))