-
Notifications
You must be signed in to change notification settings - Fork 5
/
shell sort.py
91 lines (76 loc) · 2.07 KB
/
shell sort.py
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import random
import time
N = 10000
def std_shell_sort(x):
gap_prev = 1
gap = 1
sorte = True
while True:
if gap == len(x):
break
elif gap > len(x):
gap = gap_prev
break
gap_prev = gap
gap = gap_prev * 3 + 1
while gap >= 1:
i = gap
while i <= len(x) - 1:
if x[i] < x[i - gap]:
x[i], x[i - gap] = x[i - gap], x[i]
sorte = True
i = i + 1
if sorte == False:
gap = (gap - 1) // 3
sorte = False
return x
def opt_shell_sort(x):
inc = len(x) // 2
while inc:
for i, el in enumerate(x):
while i >= inc and x[i - inc] > el:
x[i] = x[i - inc]
i -= inc
x[i] = el
inc = 1 if inc == 2 else int(inc * 5.0 / 11)
return x
if __name__ == "__main__":
a = []
b = []
c = []
for i in range(N):
a.append(i)
b.append(N - i)
c.append(random.randint(-N, N))
print("NO OPTIMIZED std_shell_sort(x)")
print("\n...SORTING ARRAY...")
st = time.time()
na = std_shell_sort(a)
end = time.time()
print("\nTIME:", (end - st), " sec")
print("\n...REVERSE ARRAY...")
st = time.time()
nb = std_shell_sort(b)
end = time.time()
print("\nTIME:", (end - st), " sec")
print("\n...RANDOM ARRAY...")
st = time.time()
nc = std_shell_sort(c)
end = time.time()
print("\nTIME:", (end - st), " sec")
print("\n\nOPTIMIZED opt_shell_sort(x)")
print("\n...SORTING ARRAY...")
st = time.time()
na = opt_shell_sort(a)
end = time.time()
print("\nTIME:", (end - st), " sec")
print("\n...REVERSE ARRAY...")
st = time.time()
nb = opt_shell_sort(b)
end = time.time()
print("\nTIME:", (end - st), " sec")
print("\n...RANDOM ARRAY...")
st = time.time()
nc = opt_shell_sort(c)
end = time.time()
print("\nTIME:", (end - st), " sec")