"""

Assign 02 -

Directions:

* Complete the sorting algorithm functions that are given below. Note that

it okay (and probably helpful) to define auxiliary/helper functions that

are called from the functions below. Refer to the README.md file for

additional info.

* NOTE: Remember to add a docstring for each function, and that a reasonable

coding style is followed (e.g. blank lines between functions).

Your program will not pass the tests if this is not done!

* Be sure that you implement your own sorting functions since.

No credit will be given if Python's built-in sort function is used.

"""

import time

import random

from math import ceil, log10

def bubbleSort(list_of_items):

start_time = time.time()

# INSERT YOUR BUBBLE SORT CODE HERE

elapsed_time = time.time() - start_time

return (list_of_items, elapsed_time)

def mergeSort(list_of_items, split_by_3=False):

start_time = time.time()

# INSERT YOUR MERGE SORT CODE HERE...

# * SPLITTING BY 2 WHEN split_by_3 = False

# * SPLITTING BY 3 WHEN split_by_3 = True

elapsed_time = time.time() - start_time

return (list_of_items, elapsed_time)

def quickSort(list_of_items, pivot_to_use='first'):

start_time = time.time()

# INSERT YOUR QUICK SORT CODE HERE...

# * USING FIRST ITEM IN THE LIST AS THE PIVOT WHEN pivot_to_use = 'first'

# * USING MIDDLE ITEM IN THE LIST AS THE PIVOT WHEN pivot_to_use != 'first'

# AND BE SURE THAT CONTINUES FOR SUBSEQUENT/RECURSIVE CALLS AS WELL

elapsed_time = time.time() - start_time

return (list_of_items, elapsed_time)

def radixSort(list_of_items, max_digits):

start_time = time.time()

# INSERT YOUR RADIX SORT CODE HERE

elapsed_time = time.time() - start_time

return (list_of_items, elapsed_time)

def assign02_main():

""" A 'main' function to be run when our program is run standalone """

list1 = list(range(5000))

random.seed(1)

random.shuffle(list1)

# list1 = [54, 26, 93, 17, 77, 31, 44, 55, 20] # helpful for early testing

# run sorting functions

bubbleRes = bubbleSort(list(list1))

mergeRes2 = mergeSort(list(list1), split_by_3=False)

mergeRes3 = mergeSort(list(list1), split_by_3=True)

quickResA = quickSort(list(list1), pivot_to_use='first')

quickResB = quickSort(list(list1), pivot_to_use='middle')

radixRes = radixSort(list(list1), ceil(log10(max(list1))))

# Print results

print(f" list1 results (randomly shuffled w/ size = {len(list1)})")

print(list1[:10])

print(f" bubbleSort time: {bubbleRes[1]:.4f} sec")

print(bubbleRes[0][:10])

print(f" mergeSort2 time: {mergeRes2[1]:.4f} sec")

print(mergeRes2[0][:10])

print(f" mergeSort3 time: {mergeRes3[1]:.4f} sec")

print(mergeRes3[0][:10])

print(f" quickSortA time: {quickResA[1]:.4f} sec")

print(quickResA[0][:10])

print(f" quickSortB time: {quickResB[1]:.4f} sec")

print(quickResB[0][:10])

print(f" radixSort time: {radixRes[1]:.4f} sec")

print(radixRes[0][:10])

# Try with a list sorted in reverse order (worst case for quicksort)

list2 = list(range(6000, 1000, -1))

# run sorting functions

bubbleRes = bubbleSort(list(list2))

mergeRes2 = mergeSort(list(list2), split_by_3=False)

mergeRes3 = mergeSort(list(list2), split_by_3=True)

quickResA = quickSort(list(list2), pivot_to_use='first')

quickResB = quickSort(list(list2), pivot_to_use='middle')

radixRes = radixSort(list(list2), ceil(log10(max(list2))))

# Print results

print(f" list2 results (sorted in reverse w/ size = {len(list2)})")

print(list2[:10])

print(f" bubbleSort time: {bubbleRes[1]:.4f} sec")

print(bubbleRes[0][:10])

print(f" mergeSort2 time: {mergeRes2[1]:.4f} sec")

print(mergeRes2[0][:10])

print(f" mergeSort3 time: {mergeRes3[1]:.4f} sec")

print(mergeRes3[0][:10])

print(f" quickSortA time: {quickResA[1]:.4f} sec")

print(quickResA[0][:10])

print(f" quickSortB time: {quickResB[1]:.4f} sec")

print(quickResB[0][:10])

print(f" radixSort time: {radixRes[1]:.4f} sec")

print(radixRes[0][:10])

# Check if the program is being run directly (i.e. not being imported)

if __name__ == '__main__':

assign02_main()