forked from AllAlgorithms/python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathshell_sort.py
More file actions
35 lines (23 loc) · 768 Bytes
/
Copy pathshell_sort.py
File metadata and controls
35 lines (23 loc) · 768 Bytes
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
"""This is a Python implementation of the shell sort algorithm
Shell sort is a variation of insertion sort. This method starts by sorting
pairs of elements far away from each other, then progressively reducing the
gap between elements to be compared.
"""
from random import randint
def shell_sort(arr):
n = len(arr)
gap = n//2
while gap > 0:
for i in range(gap, n):
tmp = arr[i]
j = i
while j >= gap and arr[j-gap] > tmp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = tmp
gap //= 2
return arr
# Tests
if __name__ == '__main__':
print(shell_sort([randint(0, 1000) for _ in range(10)]))
print(shell_sort([randint(-500, 500) for _ in range(10)]))