Start with the code in sorts.py. The file includes three sorting methods: selection, insertion, merge, and builtin (Python's built-in sort). For this problem, you must add two additional sorting functions to the file and compare the running times of all of the sorting functions on a variety of data. Make sure you use large enough and varied enough data! One of the sorting functions you must add is quicksort. The other can be any other method you find (except bubble sort). You may search the Internet (or books) for Python implementations to use. Be careful with quicksorts found on the web! It's easy to find "bad" ones - use knowledge of quicksort from lecture 31 to find a good one. The write-up will likely be several pages. It should (a) describe how you generated test data (2) include graphs, charts, and/or tables of your timing results (these must be images of things generated by Python - no hand-made graphs/charts/tables!), and (c) discuss conclusions about the relative performance of the various sorts. This should include, where appropriate, assessment of best/average/worst base behavior, and of how performance data fits with what we know about the Big-O running time bounds of these methods.

sorts.py:

def selectionSort(L): i = 0 # invariant: L[0:i] sorted and in final position while i < len(L): minIndex = findMinIndex(L, i) L[i], L[minIndex] = L[minIndex], L[i] # now L[0:i+1] sorted an in final position. i = i + 1 # L[0:i] sorted/in final position,and "loop invariant" (loop entry point assumption) holds again ## uncomment this if you want to see progress (don't do for large L though!) #print("sorted and in final pos:", L[0:i], "unsorted:", L[i:]) # return index of min item in L[startIndex:] # assumes startIndex < len(L) # def findMinIndex(L, startIndex): minIndex = startIndex currIndex = minIndex + 1 while currIndex < len(L): if L[currIndex] < L[minIndex]: minIndex = currIndex currIndex = currIndex + 1 return minIndex def insertionSort(L): i = 1 # invariant: L[0:i] is sorted while i < len(L): itemToMove = L[i] # find where itemToMove should go, shifting larger items right one slot along the way j = i-1 while ((j>=0) and (itemToMove