CS110 6.2 Preclass

quicksort.py

def swap(lst, a, b):
    lst[a], lst[b] = lst[b], lst[a]

def median(lst):
	n = len(lst)
	return sorted(lst)[n//2]

def partition(lst,low,high):
    i = ( low-1 )
    pivot = lst[high]
    for j in range(low, high):
        if   lst[j] <= pivot:
            i = i+1
            swap(lst, i, j)

    swap(lst, i+1, high)
    return ( i+1 )

def quicksort(lst,low,high):
    if low < high:
        partind = partition(lst,low,high)
        quicksort(lst, low, partind-1)
        quicksort(lst, partind+1, high)

import random
import time
random.seed(123)


start1 = time.time()

lst1 = [random.random() for a in range(100)]
quicksort(lst1, 0, len(lst1)-1)

end1 = time.time()


start2 = time.time()

lst2 = [i for i in range(100)]
quicksort(lst2, 0, len(lst2)-1)

end2 = time.time()

print("lst1:", end1-start1, "seconds")
print("lst2:", end2-start2, "seconds")