In this assignment, you will conduct a set of experiments using basic sorting algorithms.

Please see the description of the assignment in the following file: a6.pdf

Source files:

bubbleSort.py

bubbleSortB.py

insertionSort.py

selectionSort.py

quickSort.py

mergeSort.py

WHAT TO SUBMIT: Submit a report in Word or PDF format, including the tables with timings and answers to all questions. Also include some information about the machine you used to run the tests (processor type and speed, amount of memory, operating system...).

Assignment 6 Objectives: To experiment with simple sorts: selection, bubble, and insertionsorts To experiment with advanced sorts: quick, and mergesorts To start the assignment: Download the source files provided in the assignment page. The files contain the following sorting algorithms, which all sort in ascending order (i.e., from smallest to largest): 1. bubbleSort.py - bubble sort code which does not check if it can stopearly. 2. bubbleSortB.py - bubble sort code which stops early if no swapping is needed during a scan of the unsorted part. 3. insertionSort.py - the insertion sort 4. selectionSort.py - the selection sort 5. mergeSort.py the merge sort 6. quicksort.py the quick sort Files 1 to 4 run their sorting algorithm several times with different initial orderings of 10,000 list items. The initial orderings of items are: descending order, ascending order, random order, and random order again to check for consistence. Files 5 and 6 contain the sorting algorithm, but do not contain the main() function that tests the algorithm. You must add the main() function all you need to do is copy this function from one of the other files and change the name of the sort algorithm being called. You also need to copy the function shuffle(). Part 1: Simple Sort Algorithms Complete the following timings by running each program. Timings of Sorting Algorithms on 10,000 items (seconds) Sorting algorithm Initial Ordering of Items Descending Ascending Random order 1 Random order 2 bubbleSort.py bubbleSortB.py insertionSort.py selectionSort.py mergeSort.py quicksort.py Page 2 of 4 Part 2: Advanced Sort Algorithms Merge Sort The general idea of Merge Sort is as follows. Assume you have n items to sort. 1. Split the unsorted part in half to get two smaller sorting problems of size about n/2. 2. Solve both smaller problem recursively using mergesort. 3. Merge the solution to the smaller problems together to solve the original sorting problem of size n. Update your mergeSort.py to test the algorithm with larger lists of random numbers as specified in the following table. Complete the timings: Timings of Merge Sort (seconds) List size Initial Ordering of Items Descending Ascending Random order 1 Random order 2 100,000 200,000 400,000 Page 3 of 4 Quick Sort The general idea of Quick sort is as follows. Assume n items tosort. 1. Select a random item in the unsorted part as the pivot 2. Rearrange (called partitioning) the unsorted items such that: 3. Quick sort the unsorted part to the left of the pivot 4. Quick sort the unsorted part to the right of the pivot Update your quickSort.py to test the algorithm with larger lists of random numbers as specified in the following table. Complete the timings to get a feel for the speed of quicksort. Timings of Quick Sort (seconds) List size Initial Ordering of Items Descending Ascending Random order 1 Random order 2 100,000 200,000 400,000 Part 3: Questions Study the code and answer the following questions about the sorting algorithms: a) Why does the bubbleSort algorithm take less time on the ascending ordered list than the descending ordered list? b) Why does the bubbleSortB algorithm take A LOT less time on the ascending ordered list than the descending ordered list? c) Why does the insertionSort algorithm take A LOT less time on the ascending ordered list than the descending ordered list? d) Why does the insertionSort algorithm take less time on the descending ordered list than the bubbleSort algorithm on the descending ordered list? e) Why does the selectionSort algorithm take less time on the descending ordered list than the insertionSort algorithm on the descending ordered list? f) Both advanced sorting algorithms are O (n log2 n) on initially random data. Why do you suppose quick sort is the fastest advanced sort on random items? Page 4 of 4 Part 4: Bubble Sort (again) Write a variation of bubble sortthat: sorts in descending order (largest to smallest) builds the sorted part on the left-hand side of the list, i.e., Your code does NOT need to stop early if a scan of the unsorted part has no swaps. Name your function bubbleSortC Implement and test your bubbleSortC code and complete the following. Run the test 3 times. Timings of Sorting Algorithms on 10,000 items (seconds) Sorting algorithm Initial Ordering of Items Descending Ascending Random order 1 Random order 2 bubbleSortC.py, run 1 bubbleSortC.py, run 2 bubbleSortC.py, run 3 a) How does the above algorithm compare with the original bubbleSort.py?