-
Notifications
You must be signed in to change notification settings - Fork 0
/
Sorting Algorithms Runtime Analyzer.py
130 lines (103 loc) · 3.87 KB
/
Sorting Algorithms Runtime Analyzer.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
import time
from random import randint
def analyzer():
listsize = int(input("What size list do you want to create? "))
maxvalue = int(input("What is the max value of the range? "))
numrun = int(input("How many times do you want to run? "))
for i in range(1, numrun+1):
arr = []
for j in range(listsize):
arr.append(randint(1, maxvalue))
start = time.time()
def quicksort(l1):
if len(l1) < 2:
return l1
else:
pivot = l1[-1]
smaller, equal, larger = [], [], []
for num in l1:
if num < pivot:
smaller.append(num)
elif num == pivot:
equal.append(num)
else:
larger.append(num)
return quicksort(smaller) + equal + quicksort(larger)
quicksort(arr)
time1 = time.time() - start
start2 = time.time()
def mergesort(arr1, arr2):
sorted_arr = []
i = 0
j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
sorted_arr.append(arr1[i])
i += 1
else:
sorted_arr.append(arr2[j])
j += 1
if i == len(arr1):
for num in arr2[j:]:
sorted_arr.append(num)
elif j == len(arr2):
for num in arr1[i:]:
sorted_arr.append(num)
return sorted_arr
def div_arr(l1):
if len(l1) < 2:
return l1[:]
else:
middle = len(l1) // 2
arrlower = div_arr(l1[:middle])
arrupper = div_arr(l1[middle:])
return mergesort(arrlower, arrupper)
div_arr(arr)
time2 = time.time() - start2
start3 = time.time()
def bubsort(l1):
swap = True
while swap:
count = 0
for i in range(len(l1) - 1):
if l1[i] > l1[i + 1]:
l1[i], l1[i + 1] = l1[i + 1], l1[i]
swap = True
count += 1
if count == 0:
swap = False
bubsort(arr)
time3 = time.time() - start3
start4 = time.time()
def selsort(l1):
marker = 0
while marker < len(l1):
for i in range(marker, len(l1)):
if l1[i] < l1[marker]:
l1[marker], l1[i] = l1[i], l1[marker]
marker += 1
selsort(arr)
time4 = time.time() - start4
start5 = time.time()
def builtinsort(l1):
l1.sort()
builtinsort(arr)
time5 = time.time() - start5
start6 = time.time()
def inssort(l1):
key = 1
marker = 1
while marker < len(l1):
for i in range(key):
if l1[key] < l1[key - 1]:
l1[key - 1], l1[key] = l1[key], l1[key - 1]
key -= 1
marker += 1
key = marker
inssort(arr)
time6 = time.time() - start6
print("Run:", i, "\nQuicksort -> Elapsed time:", time1, "\nMergesort -> Elapsed time:", time2,
"\nBubblesort -> Elapsed time:", time3, "\nSelectionsort -> Elapsed time:", time4,
"\nBuilt-Insort -> Elapsed time:", time5, "\nInsertion Sort -> Elapsed time:", time6)
print("----------------------------------------------------------------------------------")
analyzer()