quicksorts

import random
import timeit
import sys
import resource

def quicksort_first(lst, start, end):
    comparisons = 0
    if start < end:
        pivot = start
        lst[end], lst[pivot] = lst[pivot], lst[end]
        
        p, comparisons = partition_first(lst, start, end)
        quicksort_rand(lst, start, p - 1)
        quicksort_rand(lst, p + 1, end)
    return comparisons

def partition_first(lst, start, end):
    pivot = start
    comparisons = 0
    
    lst[end], lst[pivot] = lst[pivot], lst[end]
    
    pivot_index = start - 1
    
    for index in range(start, end):
        comparisons += 1
        if lst[index] < lst[end]:
            pivot_index += 1
            lst[index], lst[pivot_index] = lst[pivot_index], lst[index]
    
    pivot_index += 1
    lst[end], lst[pivot_index] = lst[pivot_index], lst[end]
    return pivot_index, comparisons
    
def quicksort_last(lst, start, end):
    comparisons = 0
    if start < end:
        pivot = end
        lst[end], lst[pivot] = lst[pivot], lst[end]
        
        p, comparisons = partition_first(lst, start, end)
        quicksort_rand(lst, start, p - 1)
        quicksort_rand(lst, p + 1, end)
    return comparisons

def partition_last(lst, start, end):
    pivot = end
    comparisons = 0
    
    lst[end], lst[pivot] = lst[pivot], lst[end]
    
    pivot_index = start - 1
    
    for index in range(start, end):
        comparisons += 1
        if lst[index] < lst[end]:
            pivot_index += 1
            lst[index], lst[pivot_index] = lst[pivot_index], lst[index]
    
    pivot_index += 1
    lst[end], lst[pivot_index] = lst[pivot_index], lst[end]
    return pivot_index, comparisons

def quicksort_mid(lst, start, end):
    comparisons = 0
    if start < end:
        pivot = int((start + end) / 2)
        lst[end], lst[pivot] = lst[pivot], lst[end]
        
        p, comparisons = partition_first(lst, start, end)
        quicksort_rand(lst, start, p - 1)
        quicksort_rand(lst, p + 1, end)
    return comparisons

def partition_mid(lst, start, end):
    pivot = int((start + end) / 2)
    comparisons = 0
    
    lst[end], lst[pivot] = lst[pivot], lst[end]
    
    pivot_index = start - 1
    
    for index in range(start, end):
        comparisons += 1
        if lst[index] < lst[end]:
            pivot_index += 1
            lst[index], lst[pivot_index] = lst[pivot_index], lst[index]
    
    pivot_index += 1
    lst[end], lst[pivot_index] = lst[pivot_index], lst[end]
    return pivot_index, comparisons
    
def quicksort_rand(lst, start, end):
    comparisons = 0
    if start < end:
        pivot = random.randint(start, end)
        lst[end], lst[pivot] = lst[pivot], lst[end]
        
        p, comparisons = partition_rand(lst, start, end)
        quicksort_rand(lst, start, p - 1)
        quicksort_rand(lst, p + 1, end)
        

    return comparisons
        
def partition_rand(lst, start, end):
    pivot = random.randint(start, end)
    comparisons = 0
    
    lst[end], lst[pivot] = lst[pivot], lst[end]
    
    pivot_index = start - 1
    
    for index in range(start, end):
        comparisons += 1
        if lst[index] < lst[end]:
            pivot_index += 1
            lst[index], lst[pivot_index] = lst[pivot_index], lst[index]
    
    pivot_index += 1
    lst[end], lst[pivot_index] = lst[pivot_index], lst[end]
    return pivot_index, comparisons
    
def analysis():
    size = 0
    elements = [20000, 40000]
    def quicksort_rand_analysis():
        lst = [random.randrange(0, 1000, 1) for _ in range(size)]
        comparisons = quicksort_rand(lst, 0, len(lst) - 1)
        print(comparisons, end=", ")
        
    def quicksort_first_analysis():
        lst = [random.randrange(0, 1000, 1) for _ in range(size)]
        comparisons = quicksort_first(lst, 0, len(lst) - 1)
        print(comparisons, end=", ")
        
    def quicksort_last_analysis():
        lst = [random.randrange(0, 1000, 1) for _ in range(size)]
        comparisons = quicksort_last(lst, 0, len(lst) - 1)
        print(comparisons, end=", ")
        
    def quicksort_mid_analysis():
        lst = [random.randrange(0, 1000, 1) for _ in range(size)]
        comparisons = quicksort_mid(lst, 0, len(lst) - 1)
        print(comparisons, end=", ")
    
    for size in elements:
        print(size, end=", ")
        time = timeit.timeit(quicksort_rand_analysis, number = 1)
        print(time / 10**-6)
        
        print(size, end=", ")
        time = timeit.timeit(quicksort_first_analysis, number = 1)
        print(time / 10**-6)
        
        print(size, end=", ")
        time = timeit.timeit(quicksort_last_analysis, number = 1)
        print(time / 10**-6)
        
        print(size, end=", ")
        time = timeit.timeit(quicksort_mid_analysis, number = 1)
        print(time / 10**-6)
    
if __name__ == "__main__":
    analysis()