$3\mathrm{.}17$ Project $3-$ Benchmarkin$3$g Sorting Algorithms

Estimated Duration: $7$ hours

Reminder: Read through this entire project description before you begin working on it$.$

Introduction:

For this project, you will investigate the performance differences between a set of sorting algorithms. Like Project $1,$ this project is about important theoretical and practical algorithms rather than abstract data types. Sorting and searching are at the heart of many ideas and algorithms in Computer Science. Studying such algorithms will help develop your intuition for algorithm selection and design, and your ability to use Big$-$O notation to analyze and communicate about algorithms.

Part $1$: Implementation

You will be investigating $4$ algorithms

Quicksort

Mergesort

Insertion Sort

Selection Sort

Even though most of these are in$-$place, destructive sorts $($meaning that they sort the actual list, $$destroying$$ its original configuration$)-$ each function should return the sorted list, as well as the number of comparisons and swaps performed during the sort. In addition to the four sorting functions, you will also need to implement a function to determine if a given list is sorted. Here is a list of the function prototypes and descriptions for the functions our unit tests will be looking for:

boolean is$\_$sorted$($lyst$)$: This is a predicate function that returns True if lyst is sorted, False otherwise. In addition to verifying that lyst is a list, is$\_$sorted$()$ must also verify that every element in the list is an integer. If lyst is not a list, or a non$-$integer element is found in it$,$ is$\_$sorted should raise a TypeError exception. Note: We recommend implementing this function first, so that you can use it to do unit testing as you develop your sorting functions.

$($list$,$ int, int$)$ quicksort$($lyst$)$: This function implements the quicksort algorithm to sort the items in lyst$.$ the function returns a tuple containing the sorted list, followed by the number of comparisons, and finally the number of swaps performed while sorting. lyst must be a Python list containing comparable data $($i$.$e$.$ things that the $>,<,$ etc. operators can be used on to determine an ordering between two items$).$ If lyst is not a list, quicksort$()$ must raise a TypeError Exception.

$($list$,$ int, int$)$ mergesort$($lyst$)$: This function implements the mergesort algorithm to sort the items in lyst$.$ the function returns a tuple containing the sorted list, followed by the number of comparisons, and finally the number of swaps performed while sorting. lyst must be a Python list containing comparable data $($i$.$e$.$ things that the $>,<,$ etc. operators can be used on to determine an ordering between two items$).$ If lyst is not a list, mergesort$()$ must raise a TypeError Exception.

$($list$,$ int, int$)$ selection$\_$sort$($lyst$)$: This function implements the selection sort algorithm to sort the items in lyst$.$ the function returns a tuple containing the sorted list, followed by the number of comparisons, and finally the number of swaps performed while sorting. lyst must be a Python list containing comparable data $($i$.$e$.$ things that the $>,<,$ etc. operators can be used on to determine an ordering between two items$).$ If lyst is not a list, selection$\_$sort$()$ must raise a TypeError Exception.

$($list$,$ int, int$)$ insertion$\_$sort$($lyst$)$: This function implements the insertion sort algorithm to sort the items in lyst$.$ the function returns a tuple containing the sorted list, followed by the number of comparisons, and finally the number of swaps performed while sorting. lyst must be a Python list containing comparable data $($i$.$e$.$ things that the $>,<,$ etc. operators can be used on to determine an ordering between two items$).$ If lyst is not a list, insertion$\_$sort$()$ must raise a TypeError Exception.

Note $1$: Use of $"$lyst$"$ as an identifier is NOT a typo since "list" is a Python type.

Note $2$: quicksort and mergesort are typically recursive, and helper functions are often used internally. Any helper functions should be nested inside the function that uses it$,$ NOT at module scope. In this way helper functions will not be directly callable outside the parent function.

Part $2$: Validation

In order to validate the proper behavior of your search functions we highly recommend that you create a non$-$interactive $($i$.$e$.$ doesn$$t expect user arguments$/$interaction$)$ main$()$ function that conditionally executes $($see Project $2)$ and runs each of your sort algorithms on sample data. Experiment with randomized lists of different sizes and verify that you see the kinds of performance differences $($in terms of comparison and swap counts$)$ that you expect.

Note that in order to make meaningful comparisons between the performance of these different algorithms it is necessary to expose them to the same conditions $($i$.$e$.$ the same unsorted input list$($s$)).$ Since your functions "destroy" the original list in the sense that it has been sorted $-$ you will want to make a copy of your test data so that you can apply each function to a "clean" copy of the original data. Here is