Description

a) Compare:

 Write 1-2 page essay, in your own words, comparing and contrasting quicksort versus mergesort algorithms (max 12-point font). Diagrams or tables are not included in the length and your comparison must be in the form of essay. Make sure to discuss the time/space complexity, when each algorithm should be used (or not), implementation differences and similarities, etc. Submit essay as PDF or Word document to be checked by TurnItIn (not inside of a zip/rar file). Note that work which is not written in student’s own words will not earn credit. Changing words to their synonyms is not sufficient and often changes the meaning of the context or makes it read as garbage because technical terms are changed incorrectly. The submitted work must be graduate level quality and will be graded as such

Write programs for the following exercises in Python using Object Oriented approach. Each file should have your name at the top in comment, with short description of what that file is implementing. Make sure your files have appropriate names. Programs should write output to the Console and have input hardcoded in main. 

Note: Submitting wrong files or in the wrong format or corrupted files or missing files will not give you permission to re-submit. It is your responsibility to submit all the correct files on time.

b) Sort: 

1. Implement the sorting methods from the pseudo code we went over in class for Bubble sort, Insertion sort and Selection sort. Make sure to use the algorithm name as method name (e.g. bubbleSort). Write test code passing the following elements [54, 13, 2, 75, 21, 48, 2, 7] to each of the sorts and print the values after being sorted to the console. Be careful you do not pass the sorted input to the next sort!!! 

2. In the video explain each of the algorithms and implementations, run the test program and discuss the output. 

3. Capture runtime (how long it took to sort): 

 Use 3 different data sets: random values, already sorted, and sorted in opposite order of at least 2,000-10,000 elements each data set for each sorting algorithms. 

 That means run for 5 different number of elements for each data set (e.g. 2000, 4000, 6000, 8000, 10000) to compare the runtime and see a growth trend when you graph it. 

 That means you will have 3 types of datasets (random, sorted, reverse sorted) times 5 different inputs (number of elements) for a total of 15 runtime results for each algorithm.