/
Bubblesort.py
111 lines (99 loc) · 2.92 KB
/
Bubblesort.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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
def sorttime(B):
A = [randrange(1,1000) for _ in range(testsize)] # To make it create a real A for copying
numruns = 5
for i in range(len(B)):
A[i] = B[i]
time1 = datetime.now()
bubblesort(A)
time2 = datetime.now()
checkorder(A)
print "Standard Bubble Sort: Size ", testsize, ", Time: ", millis(time2 - time1)
for i in range(len(B)):
A[i] = B[i]
time1 = datetime.now()
bubblesortcheck(A)
time2 = datetime.now()
checkorder(A)
print "Swap Check Bubble Sort: Size ", testsize, ", Time: ", millis(time2 - time1)
for i in range(len(B)):
A[i] = B[i]
time1 = datetime.now()
bubblesortcheck2(A)
time2 = datetime.now()
checkorder(A)
print "Swap Check Bubble Sort 2: Size ", testsize, ", Time: ", millis(time2 - time1)
totaltime = 0
for runs in range(1, numruns):
for i in range(len(B)):
A[i] = B[i]
time1 = datetime.now()
wikipedia(A)
time2 = datetime.now()
checkorder(A)
totaltime += millis(time2-time1)
print "Wikipedia Bubble Sort: Size ", testsize, ", for ", numruns, " runs, Time: ", totaltime
totaltime = 0
for runs in range(1, numruns):
for i in range(len(B)):
A[i] = B[i]
time1 = datetime.now()
unwikipedia(A)
time2 = datetime.now()
checkorder(A)
totaltime += millis(time2-time1)
print "Wikipedia-compatible Bubble Sort without swap checking: Size ", testsize, " for ", numruns, "runs, Time: ", totaltime
# A flag check if a pass did not have any swaps, which lets us quit
def bubblesortcheck(A):
for i in range(len(A)): # Insert i'th record
swaps = False
for j in range (1, len(A) - i):
if (A[j-1] > A[j]):
swap(A, j-1, j)
swaps = True
if (not swaps):
print "Quit at ", i
break # Can quit early
# Modify the flag to check position of last swap taken
def bubblesortcheck2(A):
for i in range(len(A)-1): # Insert i'th record
lastseen = 0;
top = len(A)
for j in range(1, top-1):
if (A[j - 1] > A[j]):
swap(A, j - 1, j)
lastseen = j - 1
top = lastseen
if (top == 0):
print "Quit at ", i
break # Can quit early
# Wikipedia article "optimization" to only swap up to the last swap seen
def wikipedia(A):
n = len(A) - 1;
while (n > 0):
newn = 0
for i in range(n):
# if this pair is out of order
if (A[i] > A[i + 1]):
swap(A, i, i + 1)
newn = i
n = newn
# Wikipedia article-compatible version without swap checking
def unwikipedia(A):
n = len(A) - 1;
while (n > 0):
for i in range(n):
# if this pair is out of order
if (A[i] > A[i + 1]):
swap(A, i, i + 1)
n -= 1
def success():
print "Success! (Need to define this)"
def sorttest(A):
bubblesort(A)
#/* *** ODSATag: Bubblesort *** */
def bubblesort(A):
for i in range (len(A)): # Insert i'th record
for j in range(1, len(A) - i):
if (A[j - 1] > A[j]):
swap(A, j - 1, j)
#/* *** ODSAendTag: Bubblesort *** */