-
Notifications
You must be signed in to change notification settings - Fork 0
/
Sorts.py
238 lines (194 loc) · 7.05 KB
/
Sorts.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
import random
import time
import matplotlib.pyplot as plt
import matplotlib.animation as animation
# NOTE: Python version >=3.3 is required, due to "yield from" feature.
def swap(A, i, j):
"""Helper function to swap elements i and j of list A."""
if i != j:
A[i], A[j] = A[j], A[i]
def bubblesort(A):
"""In-place bubble sort."""
if len(A) == 1:
return
swapped = True
for i in range(len(A) - 1):
if not swapped:
break
swapped = False
for j in range(len(A) - 1 - i):
if A[j] > A[j + 1]:
swap(A, j, j + 1)
swapped = True
yield A
def insertionsort(A):
"""In-place insertion sort."""
for i in range(1, len(A)):
j = i
while j > 0 and A[j] < A[j - 1]:
swap(A, j, j - 1)
j -= 1
yield A
def mergesort(A, start, end):
"""Merge sort."""
if end <= start:
return
mid = start + ((end - start + 1) // 2) - 1
yield from mergesort(A, start, mid)
yield from mergesort(A, mid + 1, end)
yield from merge(A, start, mid, end)
yield A
def merge(A, start, mid, end):
"""Helper function for merge sort."""
merged = []
leftIdx = start
rightIdx = mid + 1
while leftIdx <= mid and rightIdx <= end:
if A[leftIdx] < A[rightIdx]:
merged.append(A[leftIdx])
leftIdx += 1
else:
merged.append(A[rightIdx])
rightIdx += 1
while leftIdx <= mid:
merged.append(A[leftIdx])
leftIdx += 1
while rightIdx <= end:
merged.append(A[rightIdx])
rightIdx += 1
for i, sorted_val in enumerate(merged):
A[start + i] = sorted_val
yield A
def quicksort(A, start, end):
"""In-place quicksort."""
if start >= end:
return
pivot = A[end]
pivotIdx = start
for i in range(start, end):
if A[i] < pivot:
swap(A, i, pivotIdx)
pivotIdx += 1
yield A
swap(A, end, pivotIdx)
yield A
yield from quicksort(A, start, pivotIdx - 1)
yield from quicksort(A, pivotIdx + 1, end)
def selectionsort(A):
"""In-place selection sort."""
if len(A) == 1:
return
for i in range(len(A)):
# Find minimum unsorted value.
minVal = A[i]
minIdx = i
for j in range(i, len(A)):
if A[j] < minVal:
minVal = A[j]
minIdx = j
yield A
swap(A, i, minIdx)
yield A
def aSort(A): # first version of a Sort
# Exceptions for this method
# ** value cannot be -ve.
# ** no repatition allowed.
# ** if a number is repeated, it will displayed only once.
# ** the height value should be less.
# ** size of resultant array is equal to the size of largest element in the original list.
# Observation
# ** time complexity dec. **
# ** space complexity inc. ***
#
B = [0 for z in range(len(A)+1)]
for i in range(0, len(A), 2):
B[A[i]] = A[i]
B[A[i+1]] = A[i+1]
yield B
# def aSort(A):
# # Exceptions for this method
# # ** no repatition allowed.
# # ** if a number is repeated, it will displayed only once.
# # ** the height value should be less.
# # ** size of resultant array is double to the size of largest element in the original list.
# # Observation
# # ** time complexity dec. ***
# # ** space complexity inc. *****
# B = [0 for z in range(len(A)*2 + 1)]
# print(B)
# for i in range(0, len(A), 1):
# if A[i] >= 0:
# B[(len(A) + A[i])] = A[i]
# else:
# B[len(A) + A[i]] = A[i]
# yield B
# print(B)
if __name__ == "__main__":
# Get user input to determine range of integers (1 to N) and desired
# sorting method (algorithm).
# N = int(input("Enter number of integers: "))
N = 100
method_msg = "Enter sorting method:\n(b)ubble\n(i)nsertion\n(m)erge \
\n(q)uick\n(s)election\n(a)sort\n"
method = input(method_msg)
# Build and randomly shuffle list of integers.
# A = [x + 1 for x in range(N)]
# random.seed(time.time())
# random.shuffle(A)
A = [51, 98, 61, 28, 20, 48, 63, 94, 42, 71, 79, 58, 87, 82, 44, 13, 34, 16, 96, 3, 97, 76, 38, 88, 8, 80, 45, 23, 21, 22, 67, 1, 55, 2, 81, 72, 73, 7, 90, 74, 24, 29, 78, 70, 89, 75, 32, 14, 84, 31,
85, 41, 62, 77, 26, 92, 10, 99, 52, 33, 25, 43, 49, 68, 18, 83, 5, 50, 35, 11, 66, 54, 12, 56, 65, 15, 86, 40, 69, 57, 64, 53, 37, 6, 100, 60, 9, 91, 46, 36, 19, 27, 47, 4, 95, 30, 17, 59, 39, 93]
# Get appropriate generator to supply to matplotlib FuncAnimation method.
if method == "b":
title = "Bubble sort"
generator = bubblesort(A)
elif method == "i":
title = "Insertion sort"
generator = insertionsort(A)
elif method == "m":
title = "Merge sort"
generator = mergesort(A, 0, N - 1)
elif method == "q":
title = "Quicksort"
generator = quicksort(A, 0, N - 1)
elif method == "a":
title = "aSort"
generator = aSort(A)
else:
title = "Selection sort"
generator = selectionsort(A)
# Initialize figure and axis.
fig, ax = plt.subplots()
ax.set_title(title)
# Initialize a bar plot. Note that matplotlib.pyplot.bar() returns a
# list of rectangles (with each bar in the bar plot corresponding
# to one rectangle), which we store in bar_rects.
bar_rects = ax.bar(range(len(A)), A, align="edge")
# Set axis limits. Set y axis upper limit high enough that the tops of
# the bars won't overlap with the text label.
ax.set_xlim(0, N)
ax.set_ylim(0, int(1.07 * N))
# Place a text label in the upper-left corner of the plot to display
# number of operations performed by the sorting algorithm (each "yield"
# is treated as 1 operation).
text = ax.text(0.02, 0.95, "", transform=ax.transAxes)
# Define function update_fig() for use with matplotlib.pyplot.FuncAnimation().
# To track the number of operations, i.e., iterations through which the
# animation has gone, define a variable "iteration". This variable will
# be passed to update_fig() to update the text label, and will also be
# incremented in update_fig(). For this increment to be reflected outside
# the function, we make "iteration" a list of 1 element, since lists (and
# other mutable objects) are passed by reference (but an integer would be
# passed by value).
# NOTE: Alternatively, iteration could be re-declared within update_fig()
# with the "global" keyword (or "nonlocal" keyword).
iteration = [0]
def update_fig(A, rects, iteration):
for rect, val in zip(rects, A):
rect.set_height(val)
iteration[0] += 1
text.set_text("# of operations: {}".format(iteration[0]))
anim = animation.FuncAnimation(fig, func=update_fig,
fargs=(
bar_rects, iteration), frames=generator, interval=1,
repeat=False)
plt.show()