SortingAlgorithms.py

"""
TODO
2nd, Because I used recursion for the Quicksort it seems to run much slower than insertion sort on the last run.
"""
#####################################################################
# Quicksort
def partition(lst, start, end):
    pivot = lst[start]
    start_i = start
    end_i = end
    
    while True:
        while pivot > lst[start_i]:
            start_i += 1
        
        while pivot <= lst[end_i] and end_i > start_i:
            end_i -= 1
        
        if start_i < end_i:
            lst[start_i], lst[end_i] = lst[end_i], lst[start_i]
        else:
            break
    
    return start_i

def quicksort_recursion(lst, start, end):
    if start >= end:
        return lst
    
    middle = partition(lst, start, end)
    lst = quicksort_recursion(lst, start, middle - 1)
    return quicksort_recursion(lst, middle + 1, end)



##### INTERFACE:
def quicksort(lst):
    return quicksort_recursion(lst, 0, len(lst) - 1)



##### Quicksort Tests
"""
print(quicksort([10, 9, 8, 7, 6, 5, 4, 3, 2, 1]))
print(quicksort([0,1,2,3,4]))
print(quicksort([1, 2, 3, 111, 3, 2, 1, 1]))


lst = []
for i in range(100):
    lst.append(random.randint(1, 1000))

print(quicksort(lst))
"""
#####################################################################

#####################################################################
##### Bubble Sort
def bubblesort(lst):
    flag = False
    it = 0
    cap = len(lst) - 1
    while flag == False:
        flag = True
        it = 0
        while it < cap:
            if lst[it] > lst[it+1]:
                lst[it + 1], lst[it] = lst[it], lst[it + 1]
                flag = False
            it += 1
    
    return lst

##### Bubble Sort Tests
"""
print(bubblesort([10, 9, 8, 7, 6, 5, 4, 3, 2, 1]))
print(bubblesort([0, 1, 2, 3, 4]))
print(bubblesort([1, 2, 3, 111, 3, 2, 1, 1]))


lst = []
for i in range(100):
    lst.append(random.randint(1, 1000))

print(bubblesort(lst))
"""
#####################################################################

#####################################################################
##### Insertion Sort
def insertionsort(lst):
    sorted_i = 0
    i = 0
    cap = len(lst)
    while sorted_i < cap:
        i = sorted_i
        while i > 0 and lst[i] < lst[i - 1]:
            lst[i], lst[i - 1] = lst[i - 1], lst[i]
            i -= 1
            
        sorted_i += 1
    
    return lst

##### Insertion Sort Tests
"""
print(insertionsort([10, 9, 8, 7, 6, 5, 4, 3, 2, 1]))
print(insertionsort([0, 1, 2, 3, 4]))
print(insertionsort([1, 2, 3, 111, 3, 2, 1, 1]))


lst = []
for i in range(100):
    lst.append(random.randint(1, 1000))

print(insertionsort(lst))
"""
#####################################################################

####### Timing Functions
import time
def timeit(func):
    start = time.time()
    func()
    end = time.time()
    return round(end - start, 3)


def get_times(lst):
    q = timeit(lambda: quicksort(lst))
    b = timeit(lambda: bubblesort(lst))
    i = timeit(lambda: insertionsort(lst))
    return q, b, i


#####################################################################

#####################################################################

###### Cases
cases = []

length = 10
for i in range(4):
    lst = []
    for j in range(length):
        lst.append(j)
        
    
    random.shuffle(lst)
    cases.append(lst)
    length *= 10

#####################################################################

#####################################################################

######## Tying it all into Codesters:
###
###

qs = []
bs = []
ii = []
labels = []
label_temp = "1"
for case in cases:
    q, b, i = get_times(case)
    qs.append(q)
    bs.append(b)
    ii.append(i)
    label_temp += "0"
    labels.append(label_temp)

table = DisplayTable("Sizes", labels, "Quick", qs, "Bubble", bs, "Insert", ii)