-
Notifications
You must be signed in to change notification settings - Fork 1
/
visual_selection_sort.py
116 lines (99 loc) · 3.5 KB
/
visual_selection_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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#!/usr/bin/python
"""
Visualizing Selection Sort.
"""
import sys, getopt
import random
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation
def init_animate():
i = 0
for rect in rects:
rect.set_height(ypos[i])
i += 1
def index_gen():
idxOfMinElement = 0
for i in range(0, samples - 1):
yield i, idxOfMinElement, -2
idxOfMinElement = i
for j in range(i + 1, samples):
k = -1
if rects[j].get_height() < rects[idxOfMinElement].get_height():
k = idxOfMinElement
idxOfMinElement = j
yield j, idxOfMinElement, k
if i == samples - 2:
yield j, idxOfMinElement, -2
def save_cnt_gen():
k = 1
for i in range(0, samples - 1):
k += 1
for j in range(i + 1, samples):
k += 1
return k
def animate(data):
i, idxOfMin, flag = data
if flag == -2:
if i > 0:
# Exchange two elements
tmp = rects[idxOfMin].get_height()
rects[idxOfMin].set_height(rects[i - 1].get_height())
rects[idxOfMin].set_color('b')
rects[idxOfMin].set_alpha(0.4)
rects[i - 1].set_height(tmp)
rects[i - 1].set_color('b')
rects[i - 1].set_alpha(0.4)
rects[samples - 1].set_color('b')
if i < samples - 1:
rects[i].set_color('y')
rects[i].set_alpha(1)
elif flag >= -1:
if flag >= 0 or i == 1:
rects[flag].set_color('b')
rects[flag].set_alpha(0.4)
if i > 1:
rects[i - 1].set_color('b')
rects[i - 1].set_alpha(0.4)
rects[i].set_color('y')
rects[i].set_alpha(0.4)
rects[idxOfMin].set_color('y')
rects[idxOfMin].set_alpha(1)
return rects
if __name__ == '__main__':
global samples, ypos, rects
if len(sys.argv) < 2:
sys.exit('missing operand\nTry \'python visual_selection_sort.py -h\' for more information.')
outputfile = ''
try:
opts, args = getopt.getopt(sys.argv[1:], "hn:o:", ["help", "number=", "ofile=", "verbose-debug"])
except getopt.GetoptError:
print('''Usage: python visual_selection_sort.py -n <number>
or: python visual_selection_sort.py -n <number> -o <outputfile>
Generate a <number> samples barchart to show how selection sort works. To directly
see the animation or save it into <outputfile>.gif file.''')
sys.exit(2)
for opt, arg in opts:
if opt in ("-h", "--help"):
print('''Usage: python visual_selection_sort.py -n <number>
or: python visual_selection_sort.py -n <number> -o <outputfile>
Generate a <number> samples barchart to show how selection sort works. To directly
see the animation or save it into <outputfile>.gif file.''')
sys.exit()
elif opt in ("-n", "--number"):
samples = int(arg)
elif opt in ("-o", "--ofile"):
outputfile = arg
fig, ax = plt.subplots()
xpos = np.arange(0, samples)
datalist = list(range(1, samples + 1))
random.shuffle(datalist)
ypos = np.asarray(datalist)
rects = ax.bar(xpos, ypos, alpha=0.4, color='b')
ani = animation.FuncAnimation(fig, animate, frames=index_gen, repeat=False,
init_func=init_animate, interval=50)
if outputfile == '':
plt.show()
else:
ani.save_count = save_cnt_gen()
ani.save(outputfile + '.gif', writer='imagemagick', fps=30, dpi=50)