I was trying to compare 3 sorting algorithm's speed - quicksort, modified quicksort, python built-in sort. So i make a loop that repeat 1000 times, generate a random list with 1000 numbers 1-1000.
my code:
import random as r
import time
def modquicksort(target):
P=len(target)-1 #modified quicksort, there is a chance that it is slower and I have no clue what I was doing
e=0
pivot=target[P]
for i in range(len(target)-1): #divide the list into, smaller, equal, and larger by pivot
if target[0]<pivot:
target.insert(P-e,target[0])
del target[0]
elif target[0]==pivot:
target.insert(P,target[0])
del target[0]
e+=1
else:
target.append(target[0])
del target[0]
P-=1
if 0<P-e-1: #normal
Lt= modquicksort(target[0:P-e])
elif 0==P-e-1: #when the "smaller" is a single element, saves one function recusive
Lt= [target[0]]
else: #when the "smaller" has no element, would cause error if you do it as normal
Lt=[]
if P<len(target)-2:
Ut= modquicksort(target[P+1:len(target)])
elif P==len(target)-1-1:
Ut= [target[len(target)-1]]
else:
Ut= []
Lt.extend(target[P-e:P+1]) #putting 3 parts together, target[P-e:P+1] is the "equal part"
Lt.extend(Ut)
return Lt
def quicksort(target): #ordinary in-place-quicksort i think, if i did if correctly
P=len(target)-1
pivot=target[P]
for i in range(len(target)-1):
if target[0]<pivot:
target.insert(P,target[0])
del target[0]
else:
target.append(target[0])
del target[0]
P-=1
if 0<P-1:
Lt= quicksort(target[0:P])
elif 0==P-1:
Lt= [target[0]]
else:
Lt=[]
if P<len(target)-2:
Ut= quicksort(target[P+1:len(target)])
elif P==len(target)-2:
Ut= [target[len(target)-1]]
else:
Ut= []
Lt.append(target[P])
Lt.extend(Ut)
return Lt
def randomlist(size=1000,min=0,max=1000):
list=[]
for i in range(size):
list.append(r.randrange(min,max))
return list
#battle time!
time1=0
time2=0
time3=0
n=1000 #1000 runs slower enough for me
thelist=[]
for i in range(n):
thelist=randomlist()
start2=time.time()
sort2=quicksort(thelist)
time2+=time.time()-start2
sort3=thelist
start3=time.time()
sort3.sort()
time3+=time.time()-start3
start1=time.time()
sort1=modquicksort(thelist)
time1+=time.time()-start1
avg1=time1/n
avg2=time2/n
avg3=time3/n
print(f"modified quicksort process time(avg): {avg1} s")
print(f"normal quicksort process time(avg): {avg2} s")
print(f"built-in sort process time(avg): {avg3} s")
print("test if they work:(print 10 first elements)")
print(f"modified quicksort {sort1[0:10]}")
print(f"normal quicksort {sort2[0:10]}")
print(f"built-in sort {sort3[0:10]}")
look at below specifically. If i swap these, the measured time will be different
start1=time.time()
sort1=modquicksort(thelist)
time1+=time.time()-start1
start2=time.time()
sort2=quicksort(thelist)
time2+=time.time()-start2
sort3=thelist
start3=time.time()
sort3.sort()
time3+=time.time()-start3
for example, this is the output of 1->2->3:
modified quicksort process time(avg): 0.00194879150390625 s
normal quicksort process time(avg): 0.0022293198108673095 s
built-in sort process time(avg): 6.503438949584961e-05 s
test if they work:(print 10 first elements)
modified quicksort [0, 0, 0, 1, 2, 4, 5, 5, 5, 7]
normal quicksort [0, 0, 0, 1, 2, 4, 5, 5, 5, 7]
built-in sort [0, 0, 0, 1, 2, 4, 5, 5, 5, 7]
however, if I make it 2->3->1: it became
modified quicksort process time(avg): 0.053626694202423095 s
normal quicksort process time(avg): 0.001788553237915039 s
built-in sort process time(avg): 6.534552574157715e-05 s
test if they work:(print 10 first elements)
modified quicksort [0, 3, 3, 6, 6, 7, 8, 10, 12, 12]
normal quicksort [0, 3, 3, 6, 6, 7, 8, 10, 12, 12]
built-in sort [0, 3, 3, 6, 6, 7, 8, 10, 12, 12]
modified quicksort process time; 0.0019 to 0.0536
output of same sort1,sort2,sort3 order is consistent but swapping them change the result, it shouldn't happen
I tried time.process_time() and time.perf_counter() instead of time.time(). It doesn't fix the issue. I was trying to make it show the correct time elapse. But the result wasn't even consistent right now.
edit: I watch Mcoding's video and he said orders matters so i shuffle the order by
permuations=[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
for i in range(n):
thelist=randomlist()
order=permuations[r.randint(0,5)]
for i in order:
if i==1:
start1=time.perf_counter()
sort1=modquicksort(thelist)
time1+=time.perf_counter()-start1
if i==2:
start2=time.perf_counter()
sort2=quicksort(thelist)
time2+=time.perf_counter()-start2
if i==3:
sort3=thelist
start3=time.perf_counter()
sort3.sort()
time3+=time.perf_counter()-start3
and it works! If you want to know the result of testing. My modified quicksort is generally slightly slower than normal quicksort. And python built-in sort is 100x faster idk how.(how does it sort so fast?) Also if the number range of the list is less than 15% of the list length, my modified quicksort would be a lot faster.
I still have problem on how to make these type of test better and how to optimize sorting lol. Please tell me.