Skip to content

Commit c78e569

Browse files
joeyajamesjoeyajames
authored
moved all Python sorting algorithms into 1 folder
1 parent fe3e849 commit c78e569

File tree

6 files changed

+556
-0
lines changed

6 files changed

+556
-0
lines changed

‎Sorting Algorithms/SortingAlgorithms

Lines changed: 394 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,394 @@
1+
import random
2+
import time
3+
import copy
4+
size1 = 100
5+
size2 = 10000
6+
size3 = 1000000
7+
span = 1000000
8+
threshold = 20
9+
10+
#---------------------------------------
11+
# Insertion Sort
12+
#---------------------------------------
13+
# not optimized, equiv to while version below, but uses for loop
14+
def insertion_sort1(A):
15+
for i in range(1, len(A)):
16+
for j in range(i-1, -1, -1):
17+
if A[j] > A[j+1]:
18+
A[j], A[j+1] = A[j+1], A[j]
19+
else:
20+
break
21+
22+
# not optimized, equiv to break version, but uses while loop
23+
def insertion_sort2(A):
24+
for i in range(1, len(A)):
25+
j = i-1
26+
while A[j] > A[j+1] and j >= 0:
27+
A[j], A[j+1] = A[j+1], A[j]
28+
j -= 1
29+
30+
# optimized - shifts instead of swapping
31+
def insertion_sort3(A):
32+
for i in range(1, len(A)):
33+
curNum = A[i]
34+
k = 0
35+
for j in range(i-1, -2, -1):
36+
k = j
37+
if A[j] > curNum:
38+
A[j+1] = A[j]
39+
else:
40+
break
41+
A[k+1] = curNum
42+
43+
#---------------------------------------
44+
# Selection Sort
45+
#---------------------------------------
46+
def selection_sort(A):
47+
for i in range (0, len(A) - 1):
48+
minIndex = i
49+
for j in range (i+1, len(A)):
50+
if A[j] < A[minIndex]:
51+
minIndex = j
52+
if minIndex != i:
53+
A[i], A[minIndex] = A[minIndex], A[i]
54+
55+
#---------------------------------------
56+
# Bubble Sort
57+
#---------------------------------------
58+
# not optimized
59+
def bubble_sort1(A):
60+
for i in range (0, len(A) - 1):
61+
for j in range (0, len(A) - i - 1):
62+
if A[j] > A[j+1]:
63+
A[j], A[j+1] = A[j+1], A[j]
64+
65+
# optimized to exit if no swaps occur
66+
def bubble_sort2(A):
67+
for i in range (0, len(A) - 1):
68+
done = True
69+
for j in range (0, len(A) - i - 1):
70+
if A[j] > A[j+1]:
71+
A[j], A[j+1] = A[j+1], A[j]
72+
done = False
73+
if done:
74+
return
75+
76+
#---------------------------------------
77+
# Merge Sort
78+
#---------------------------------------
79+
def merge_sort(A):
80+
merge_sort2(A, 0, len(A)-1)
81+
82+
def merge_sort2(A, first, last):
83+
if last-first < threshold and first < last:
84+
quick_selection(A, first, last)
85+
elif first < last:
86+
middle = (first + last)//2
87+
merge_sort2(A, first, middle)
88+
merge_sort2(A, middle+1, last)
89+
merge(A, first, middle, last)
90+
91+
def merge(A, first, middle, last):
92+
L = A[first:middle]
93+
R = A[middle:last+1]
94+
L.append(999999999)
95+
R.append(999999999)
96+
i = j = 0
97+
98+
for k in range (first, last+1):
99+
if L[i] <= R[j]:
100+
A[k] = L[i]
101+
i += 1
102+
else:
103+
A[k] = R[j]
104+
j += 1
105+
#---------------------------------------
106+
# Quick Sort
107+
#---------------------------------------
108+
def quick_sort(A):
109+
quick_sort2(A, 0, len(A)-1)
110+
111+
def quick_sort2(A, low, hi):
112+
if hi-low < threshold and low < hi:
113+
quick_selection(A, low, hi)
114+
elif low < hi:
115+
p = partition(A, low, hi)
116+
quick_sort2(A, low, p - 1)
117+
quick_sort2(A, p + 1, hi)
118+
119+
def get_pivot(A, low, hi):
120+
mid = (hi + low) // 2
121+
s = sorted([A[low], A[mid], A[hi]])
122+
if s[1] == A[low]:
123+
return low
124+
elif s[1] == A[mid]:
125+
return mid
126+
return hi
127+
128+
def partition(A, low, hi):
129+
pivotIndex = get_pivot(A, low, hi)
130+
pivotValue = A[pivotIndex]
131+
A[pivotIndex], A[low] = A[low], A[pivotIndex]
132+
border = low
133+
134+
for i in range(low, hi+1):
135+
if A[i] < pivotValue:
136+
border += 1
137+
A[i], A[border] = A[border], A[i]
138+
A[low], A[border] = A[border], A[low]
139+
140+
return (border)
141+
142+
def quick_selection(x, first, last):
143+
for i in range (first, last):
144+
minIndex = i
145+
for j in range (i+1, last+1):
146+
if x[j] < x[minIndex]:
147+
minIndex = j
148+
if minIndex != i:
149+
x[i], x[minIndex] = x[minIndex], x[i]
150+
151+
#--------------RANDOM ORDER----------------------
152+
#------------------------------------------------
153+
# size = 100
154+
#------------------------------------------------
155+
print("\nRandom Order\n---------------------------------")
156+
w = [random.randint(0, span) for a in range(0, size1)]
157+
t1 = time.clock()
158+
insertion_sort3(w)
159+
print("Insertion Sort(size=", str(size1),"): ", (time.clock()-t1) * 1000)
160+
161+
w = [random.randint(0, span) for a in range(0, size1)]
162+
t1 = time.clock()
163+
selection_sort(w)
164+
print("Selection Sort(size=", str(size1),"): ", (time.clock()-t1) * 1000)
165+
166+
w = [random.randint(0, span) for a in range(0, size1)]
167+
t1 = time.clock()
168+
bubble_sort2(w)
169+
print("Bubble Sort(size=", str(size1),"): ", (time.clock()-t1) * 1000)
170+
171+
w = [random.randint(0, span) for a in range(0, size1)]
172+
t1 = time.clock()
173+
merge_sort(w)
174+
print("Merge Sort(size=", str(size1),"): ", (time.clock()-t1) * 1000)
175+
176+
w = [random.randint(0, span) for a in range(0, size1)]
177+
t1 = time.clock()
178+
quick_sort(w)
179+
print("Quick Sort(size=", str(size1),"): ", (time.clock()-t1) * 1000)
180+
181+
w = [random.randint(0, span) for a in range(0, size1)]
182+
t1 = time.clock()
183+
w.sort()
184+
print("Tim Sort(size=", str(size1),"): ", (time.clock()-t1) * 1000)
185+
#------------------------------------------------
186+
# size = 10,000
187+
#------------------------------------------------
188+
w = [random.randint(0, span) for a in range(0, size2)]
189+
t1 = time.clock()
190+
insertion_sort3(w)
191+
print("Insertion Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
192+
193+
w = [random.randint(0, span) for a in range(0, size2)]
194+
t1 = time.clock()
195+
selection_sort(w)
196+
print("Selection Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
197+
198+
w = [random.randint(0, span) for a in range(0, size2)]
199+
t1 = time.clock()
200+
bubble_sort2(w)
201+
print("Bubble Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
202+
203+
w = [random.randint(0, span) for a in range(0, size2)]
204+
t1 = time.clock()
205+
merge_sort(w)
206+
print("Merge Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
207+
208+
w = [random.randint(0, span) for a in range(0, size2)]
209+
t1 = time.clock()
210+
quick_sort(w)
211+
print("Quick Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
212+
213+
w = [random.randint(0, span) for a in range(0, size2)]
214+
t1 = time.clock()
215+
w.sort()
216+
print("Tim Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
217+
#------------------------------------------------
218+
# size = 1,000,000
219+
#------------------------------------------------
220+
w = [random.randint(0, span) for a in range(0, size3)]
221+
t1 = time.clock()
222+
merge_sort(w)
223+
print("Merge Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
224+
225+
w = [random.randint(0, span) for a in range(0, size3)]
226+
t1 = time.clock()
227+
quick_sort(w)
228+
print("Quick Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
229+
230+
w = [random.randint(0, span) for a in range(0, size3)]
231+
t1 = time.clock()
232+
w.sort()
233+
print("Tim Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
234+
235+
# ----------------ALREADY SORTED-----------------
236+
#------------------------------------------------
237+
# size = 10,000
238+
#------------------------------------------------
239+
print("\nAlready Sorted\n---------------------------------")
240+
241+
w = [a for a in range(0, size2)]
242+
t1 = time.clock()
243+
insertion_sort3(w)
244+
print("Insertion Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
245+
246+
t1 = time.clock()
247+
selection_sort(w)
248+
print("Selection Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
249+
250+
t1 = time.clock()
251+
bubble_sort2(w)
252+
print("Bubble Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
253+
254+
t1 = time.clock()
255+
merge_sort(w)
256+
print("Merge Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
257+
258+
t1 = time.clock()
259+
quick_sort(w)
260+
print("Quick Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
261+
262+
t1 = time.clock()
263+
w.sort()
264+
print("Tim Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
265+
#------------------------------------------------
266+
# size = 1,000,000
267+
#------------------------------------------------
268+
w = [a for a in range(0, size3)]
269+
t1 = time.clock()
270+
merge_sort(w)
271+
print("Merge Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
272+
273+
t1 = time.clock()
274+
quick_sort(w)
275+
print("Quick Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
276+
277+
t1 = time.clock()
278+
w.sort()
279+
print("Tim Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
280+
281+
# ----------------REVERSE SORTED-----------------
282+
#------------------------------------------------
283+
# size = 10,000
284+
#------------------------------------------------
285+
print("\nReverse Sorted\n---------------------------------")
286+
287+
w = [a for a in range(0, size2)]
288+
w.reverse()
289+
t1 = time.clock()
290+
insertion_sort3(w)
291+
print("Insertion Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
292+
293+
w = [a for a in range(0, size2)]
294+
w.reverse()
295+
t1 = time.clock()
296+
selection_sort(w)
297+
print("Selection Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
298+
299+
w = [a for a in range(0, size2)]
300+
w.reverse()
301+
t1 = time.clock()
302+
bubble_sort2(w)
303+
print("Bubble Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
304+
305+
w = [a for a in range(0, size2)]
306+
w.reverse()
307+
t1 = time.clock()
308+
merge_sort(w)
309+
print("Merge Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
310+
311+
w = [a for a in range(0, size2)]
312+
w.reverse()
313+
t1 = time.clock()
314+
quick_sort(w)
315+
print("Quick Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
316+
317+
w = [a for a in range(0, size2)]
318+
w.reverse()
319+
t1 = time.clock()
320+
w.sort()
321+
print("Tim Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
322+
#------------------------------------------------
323+
# size = 1,000,000
324+
#------------------------------------------------
325+
w = [a for a in range(0, size3)]
326+
w.reverse()
327+
t1 = time.clock()
328+
merge_sort(w)
329+
print("Merge Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
330+
331+
w = [a for a in range(0, size3)]
332+
w.reverse()
333+
t1 = time.clock()
334+
quick_sort(w)
335+
print("Quick Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
336+
337+
w = [a for a in range(0, size3)]
338+
w.reverse()
339+
t1 = time.clock()
340+
w.sort()
341+
print("Tim Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
342+
343+
#--------------RANDOM ORDER, MANY DUPLICATES------------------
344+
#------------------------------------------------
345+
# size = 10,000
346+
#------------------------------------------------
347+
print("\nRandom Order, Many Duplicates\n---------------------------------")
348+
349+
w = [random.randint(0, size2//10) for a in range(0, size2)]
350+
t1 = time.clock()
351+
insertion_sort3(w)
352+
print("Insertion Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
353+
354+
w = [random.randint(0, size2//10) for a in range(0, size2)]
355+
t1 = time.clock()
356+
selection_sort(w)
357+
print("Selection Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
358+
359+
w = [random.randint(0,size2//10) for a in range(0, size2)]
360+
t1 = time.clock()
361+
bubble_sort2(w)
362+
print("Bubble Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
363+
364+
w = [random.randint(0, size2//10) for a in range(0, size2)]
365+
t1 = time.clock()
366+
merge_sort(w)
367+
print("Merge Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
368+
369+
w = [random.randint(0, size2//10) for a in range(0, size2)]
370+
t1 = time.clock()
371+
quick_sort(w)
372+
print("Quick Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
373+
374+
w = [random.randint(0, size2//10) for a in range(0, size2)]
375+
t1 = time.clock()
376+
w.sort()
377+
print("Tim Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
378+
#------------------------------------------------
379+
# size = 1,000,000
380+
#------------------------------------------------
381+
w = [random.randint(0, size2//10) for a in range(0, size3)]
382+
t1 = time.clock()
383+
merge_sort(w)
384+
print("Merge Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
385+
386+
w = [random.randint(0, size2//10) for a in range(0, size3)]
387+
t1 = time.clock()
388+
#quick_sort(w)
389+
#print("Quick Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
390+
391+
w = [random.randint(0, size2//10) for a in range(0, size3)]
392+
t1 = time.clock()
393+
w.sort()
394+
print("Tim Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)

0 commit comments

Comments
 (0)