-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathalgorithms.py
More file actions
130 lines (111 loc) · 4.66 KB
/
algorithms.py
File metadata and controls
130 lines (111 loc) · 4.66 KB
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
# algorithms.py
import time
def bubble_sort(data, draw_data, tick_time):
for i in range(len(data) - 1):
for j in range(len(data) - i - 1):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
draw_data(data, [x if x != j and x != j + 1 else 'red' for x in range(len(data))])
time.sleep(tick_time)
draw_data(data, ['green' for _ in range(len(data))])
def selection_sort(data, draw_data, tick_time):
for i in range(len(data)):
min_idx = i
for j in range(i + 1, len(data)):
if data[j] < data[min_idx]:
min_idx = j
draw_data(data, ['red' if x == j else 'yellow' if x == i else 'blue' for x in range(len(data))])
time.sleep(tick_time)
data[i], data[min_idx] = data[min_idx], data[i]
draw_data(data, ['green' if x <= i else 'blue' for x in range(len(data))])
time.sleep(tick_time)
draw_data(data, ['green' for _ in range(len(data))])
def insertion_sort(data, draw_data, tick_time):
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and key < data[j]:
data[j + 1] = data[j]
j -= 1
draw_data(data, ['red' if x == j or x == i else 'yellow' for x in range(len(data))])
time.sleep(tick_time)
data[j + 1] = key
draw_data(data, ['green' if x <= i else 'blue' for x in range(len(data))])
time.sleep(tick_time)
draw_data(data, ['green' for _ in range(len(data))])
def merge_sort(data, draw_data, tick_time):
merge_sort_alg(data, 0, len(data) - 1, draw_data, tick_time)
def merge_sort_alg(data, left, right, draw_data, tick_time):
if left < right:
mid = (left + right) // 2
merge_sort_alg(data, left, mid, draw_data, tick_time)
merge_sort_alg(data, mid + 1, right, draw_data, tick_time)
merge(data, left, mid, right, draw_data, tick_time)
def merge(data, left, mid, right, draw_data, tick_time):
left_copy = data[left:mid + 1]
right_copy = data[mid + 1:right + 1]
i = j = 0
k = left
while i < len(left_copy) and j < len(right_copy):
if left_copy[i] <= right_copy[j]:
data[k] = left_copy[i]
i += 1
else:
data[k] = right_copy[j]
j += 1
k += 1
draw_data(data, ['green' if x >= left and x <= right else 'blue' for x in range(len(data))])
time.sleep(tick_time)
while i < len(left_copy):
data[k] = left_copy[i]
i += 1
k += 1
draw_data(data, ['green' if x >= left and x <= right else 'blue' for x in range(len(data))])
time.sleep(tick_time)
while j < len(right_copy):
data[k] = right_copy[j]
j += 1
k += 1
draw_data(data, ['green' if x >= left and x <= right else 'blue' for x in range(len(data))])
time.sleep(tick_time)
def quick_sort(data, draw_data, tick_time):
quick_sort_alg(data, 0, len(data) - 1, draw_data, tick_time)
def quick_sort_alg(data, low, high, draw_data, tick_time):
if low < high:
pi = partition(data, low, high, draw_data, tick_time)
quick_sort_alg(data, low, pi - 1, draw_data, tick_time)
quick_sort_alg(data, pi + 1, high, draw_data, tick_time)
def partition(data, low, high, draw_data, tick_time):
pivot = data[high]
i = low - 1
for j in range(low, high):
if data[j] < pivot:
i += 1
data[i], data[j] = data[j], data[i]
draw_data(data, ['green' if x == i or x == j else 'yellow' if x == high else 'blue' for x in range(len(data))])
time.sleep(tick_time)
data[i + 1], data[high] = data[high], data[i + 1]
draw_data(data, ['green' if x == i + 1 else 'blue' for x in range(len(data))])
return i + 1
def heap_sort(data, draw_data, tick_time):
n = len(data)
for i in range(n // 2 - 1, -1, -1):
heapify(data, n, i, draw_data, tick_time)
for i in range(n - 1, 0, -1):
data[i], data[0] = data[0], data[i]
draw_data(data, ['green' if x == i else 'blue' for x in range(len(data))])
time.sleep(tick_time)
heapify(data, i, 0, draw_data, tick_time)
def heapify(data, n, i, draw_data, tick_time):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and data[left] > data[largest]:
largest = left
if right < n and data[right] > data[largest]:
largest = right
if largest != i:
data[i], data[largest] = data[largest], data[i]
draw_data(data, ['red' if x == i or x == largest else 'blue' for x in range(len(data))])
time.sleep(tick_time)
heapify(data, n, largest, draw_data, tick_time)