Measured time inconsistent on swapping measuring order

61 views Asked by At

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.

0

There are 0 answers