-
Notifications
You must be signed in to change notification settings - Fork 1
/
SortingAlgorithVisualizer.py
280 lines (219 loc) · 9 KB
/
SortingAlgorithVisualizer.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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
import pygame
import random
import math
pygame.init()
class DrawInformation:
BLACK = 0, 0, 0
WHITE = 255, 255, 255
# GREEN = 0, 255, 0
GREEN = 50, 205, 50
RED = 255, 0, 0
BACKGROUND_COLOR = WHITE
GRADIENT = [
(128, 128, 128),
(160, 160, 160),
(192, 192, 192)
]
FONT = pygame.font.SysFont('calibri', 25)
LARGE_FONT = pygame.font.SysFont('calibri', 30)
SIDE_PAD = 100
TOP_PAD = 150
def __init__(self, width, height, lst):
self.width = width
self.height = height
self.window = pygame.display.set_mode((width, height))
pygame.display.set_caption("Sorting Algorithm Visualization")
self.set_list(lst)
def set_list(self, lst):
self.lst = lst
self.min_val = min(lst)
self.max_val = max(lst)
self.block_width = round((self.width - self.SIDE_PAD) / len(lst))
self.block_height = math.floor((self.height - self.TOP_PAD) / (self.max_val - self.min_val))
self.start_x = self.SIDE_PAD // 2
def draw(draw_info, algo_name, ascending):
draw_info.window.fill(draw_info.BACKGROUND_COLOR)
title = draw_info.LARGE_FONT.render(f"{algo_name} - {'Ascending' if ascending else 'Descending'}", 1, draw_info.GREEN)
draw_info.window.blit(title, (draw_info.width / 2 - title.get_width() / 2, 5))
controls = draw_info.FONT.render("R - Reset | SPACE - Start Sorting | A - Ascending | D - Descending", 1, draw_info.BLACK)
draw_info.window.blit(controls, (draw_info.width/2 - controls.get_width()/2, 45))
controls = draw_info.FONT.render("1 - Decrease Speed | 2 - Increase Speed | 3 - Reset Speed", 1, draw_info.BLACK)
draw_info.window.blit(controls, (draw_info.width/2 - controls.get_width()/2, 75))
sorting = draw_info.FONT.render("I - Insertion Sort | B - Bubble Sort | S - Selection Sort | H - Heap Sort", 1, draw_info.BLACK)
draw_info.window.blit(sorting, (draw_info.width / 2 - sorting.get_width() / 2, 105))
# sorting = draw_info.FONT.render("I - Insertion Sort | B - Bubble Sort | S - Selection Sort | H - Heap Sort", 1, draw_info.BLACK)
# draw_info.window.blit(sorting, (draw_info.width / 2 - sorting.get_width() / 2, 75))
draw_list(draw_info)
pygame.display.update()
def draw_list(draw_info, color_positions={}, clear_bg=False):
lst = draw_info.lst
if clear_bg:
clear_rect = (draw_info.SIDE_PAD//2, draw_info.TOP_PAD, draw_info.width - draw_info.SIDE_PAD, draw_info.height - draw_info.TOP_PAD)
pygame.draw.rect(draw_info.window, draw_info.BACKGROUND_COLOR, clear_rect)
for i, val in enumerate(lst):
x = draw_info.start_x + i * draw_info.block_width
y = draw_info.height - (val - draw_info.min_val) * draw_info.block_height
color = draw_info.GRADIENT[i % 3]
if i in color_positions:
color = color_positions[i]
pygame.draw.rect(draw_info.window, color, (x, y, draw_info.block_width, draw_info.height) )
if clear_bg:
pygame.display.update()
def generate_starting_list(n, min_val, max_val):
lst = []
for i in range(n):
val = random.randint(min_val, max_val)
lst.append(val)
return lst
def bubble_sort(draw_info, ascending =True):
lst = draw_info.lst
for i in range(len(lst) - 1):
for j in range(len(lst) - 1 - i):
num1 = lst[j]
num2 = lst[j + 1]
if (num1 > num2 and ascending) or (num1 < num2 and not ascending):
lst[j], lst[j+1] = lst[j+1], lst[j]
draw_list(draw_info, {j: draw_info.GREEN, j+1: draw_info.RED}, True)
yield True
return lst
def insertion_sort(draw_info, ascending=True):
lst = draw_info.lst
for i in range(1, len(lst)):
current = lst[i]
while True:
ascending_sort = i > 0 and lst[i - 1] > current and ascending
descending_sort = i > 0 and lst[i - 1] < current and not ascending
if not ascending_sort and not descending_sort:
break
lst[i] = lst[i - 1]
i = i - 1
lst[i] = current
draw_list(draw_info, {i-1: draw_info.GREEN, i: draw_info.RED}, True)
yield True
return lst
def selection_sort(draw_info, ascending=True):
lst = draw_info.lst
if ascending:
for i in range(len(lst)):
# Find the minimum element in remaining
# unsorted lstay
min_idx = i
for j in range(i + 1, len(lst)):
if lst[min_idx] > lst[j]:
min_idx = j
# Swap the found minimum element with
# the first element
lst[i], lst[min_idx] = lst[min_idx], lst[i]
draw_list(draw_info, {i: draw_info.GREEN, min_idx: draw_info.RED}, True)
yield True
return lst
if not ascending:
for i in range(len(lst)):
# Find the minimum element in remaining
# unsorted lstay
max_idx = i
for j in range(i + 1, len(lst)):
if lst[max_idx] < lst[j]:
max_idx = j
# Swap the found minimum element with
# the first element
lst[i], lst[max_idx] = lst[max_idx], lst[i]
draw_list(draw_info, {i: draw_info.GREEN, max_idx: draw_info.RED}, True)
yield True
return lst
def heap_sort(draw_info, ascending=True):
def heapify(lst, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
# See if left child of root exists and is
# greater than root
if l < n and ((lst[i] < lst[l] and ascending) or (lst[i] > lst[l] and not ascending)):
largest = l
# See if right child of root exists and is
# greater than root
if r < n and ((lst[largest] < lst[r] and ascending) or (lst[largest] > lst[r] and not ascending)):
largest = r
# Change root, if needed
if largest != i:
lst[i], lst[largest] = lst[largest], lst[i] # swap
draw_list(draw_info, {i: draw_info.GREEN, largest: draw_info.RED}, True)
# yield True
# Heapify the root.
heapify(lst, n, largest)
# The main function to sort an lstay of given size
lst = draw_info.lst
n = len(lst)
# Build a maxheap.
# Since last parent will be at ((n//2)-1) we can start at that location.
for i in range(n // 2 - 1, -1, -1):
heapify(lst, n, i)
# One by one extract elements
for i in range(n - 1, 0, -1):
lst[i], lst[0] = lst[0], lst[i] # swap
draw_list(draw_info, {i: draw_info.GREEN, 0: draw_info.RED}, True)
yield True
heapify(lst, i, 0)
return lst
def main():
run = True
clock = pygame.time.Clock()
n = 50
min_val = 0
max_val = 100
speed = 51
lst = generate_starting_list(n, min_val, max_val)
draw_info = DrawInformation(800, 600, lst)
sorting = False
ascending = True
sorting_algorithm = bubble_sort
sorting_algo_name = "Bubble Sort"
sorting_algorithm_generator = None
while run:
clock.tick(speed)
if sorting:
try:
next(sorting_algorithm_generator)
except StopIteration:
sorting = False
else:
draw(draw_info, sorting_algo_name, ascending)
for event in pygame.event.get():
if event.type == pygame.QUIT:
run = False
if event.type != pygame.KEYDOWN:
continue
if event.key == pygame.K_r:
lst = generate_starting_list(n, min_val, max_val)
draw_info.set_list(lst)
sorting = False
elif event.key == pygame.K_1:
if speed > 1:
speed -= 10
elif event.key == pygame.K_2:
if speed < 120:
speed += 10
elif event.key == pygame.K_3:
speed = 51
elif event.key == pygame.K_SPACE and sorting == False:
sorting = True
sorting_algorithm_generator = sorting_algorithm(draw_info, ascending)
elif event.key == pygame.K_a and not sorting:
ascending = True
elif event.key == pygame.K_d and not sorting:
ascending = False
elif event.key == pygame.K_i and not sorting:
sorting_algorithm = insertion_sort
sorting_algo_name = "Insertion Sort"
elif event.key == pygame.K_b and not sorting:
sorting_algorithm = bubble_sort
sorting_algo_name = "Bubble Sort"
elif event.key == pygame.K_s and not sorting:
sorting_algorithm = selection_sort
sorting_algo_name = "Selection Sort"
elif event.key == pygame.K_h and not sorting:
sorting_algorithm = heap_sort
sorting_algo_name = "Heap Sort"
pygame.quit()
if __name__ == '__main__':
main()