quicksort cs110.py

# coding: utf-8

# In[2]:


##define partition algorithm
    
#takes array and start and end indices as input
def partition(A, p, r):
    
    #defines pivot as the last value in the subarray
    x = A[r]
    
    #defines i as the element before the first in the array
    i = p - 1
    
    #iterates through all values including p up to r
    for j in range(p, r):
        
        #tests if the value is less than or equal to pivot
        if A[j] <= x:
            
            #if it is, i is incremented by 1
            i += 1
            
            #and A[i], which we know is greater than x, is switched with A[j] 
            A[i], A[j] = A[j], A[i]
            
    #when the loop terminates, all values within A[p...i] are less than x
    #so we switch x with A, putting the pivot in its proper place
    A[i + 1], A[r] = A[r], A[i + 1]
    
    #returns value that will define next partition
    return i + 1


# In[3]:


##defines quicksort

#takes array and start and end indices as input
def quicksort(A, p, r):
    
    #as long as the subarray is longer than 0
    if p < r:
        #partitions the subarray
        q = partition(A, p, r)
        
        #recursivley call quicksort on two new subarrays
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)


# In[11]:


##generate random test list

import random

random.seed(123)

lst1 = [random.random() for a in range(100000)]


# In[12]:


##test quicksort on random list

quicksort(lst1, 0, len(lst1) - 1)
print(lst1) #appears sorted


# In[13]:


##generate ordered list
lst2 = list(range(100000)


# In[ ]:


##test quicksort on ordered list

quicksort(lst2, 0, len(lst2) - 1)
print(lst2) #appears sorted


# In[4]:


##defines fibonacci function

def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)


# In[ ]:


##runtime for fib(100) vs. quicksort(n=100)

import time 

#generate test lengths
ns = list(range(1, 101))

#initialize lists to store runtimes
fib_times = []
quick_times = []

#measure runtime for each algorithm and compare
for i in [100]:
    print(i)
    #test list for quicksort
    this_list = list(range(i))
    
    this_quick_time = 0
    this_fib_time = 0
    
    for j in range(30):
        
        fib_start = time.time()
        fib(i)
        fib_end = time.time()
        this_fib_time += (fib_end - fib_start)
        
        #fib_times.append(fib_end - fib_start)
        print("fib done")
        quick_start = time.time()
        quicksort(this_list, 0, len(this_list) - 1)
        quick_end = time.time()
        print("quick done")
        this_quick_time += (quick_end - quick_start)
        #quick_times.append(quick_end - quick_start)