In this lab you are going to implement various sorting algorithms we discussed. You will also compare their performances.
Create an integer array of size S. Fill in the array with random numbers n where 1,000,000≥n≥0. Apply each of the following sorting algorithms to sort the array
- Bubble Sort
- Selection Sort
- Insertion Sort
- Shell Sort
- Merge Sort
- Quick Sort with pivot as the middle element
- Quick Sort with pivot as the median of the first, last and middle elements of the array
- Quick Sort with pivot as a random element of the array (use the rand function to choose a random arrray index)
Before applying each algorithm, initialize the array to the original state (randomly filled values) by saving a copy of the original array. After applying each sort function print out the first 20 elements of the array to make sure that it is really sorted (your sort algorithm is working correctly).
Also measure and report the (CPU) time each algorithm takes. You can see how to time code in this code. For each run output a table of results showing the sort type, first 20 elements, the number of comparisons done, and the number of seconds taken.
Create a loop that repeats this test process for arrays of size S where S = i* 10,000 for i =1, 2, 4, 6, 8.
I have included a function measureTime that you can call and pass a sort and data to, it will run the sort and time it.
Create a list of sorting functions, and iterate over the list. I have started it for you.
Turn in:
- Submit Github url
- Include output of the tests.
Grading:
| Category | Description | Points | Score |
| Correct Implementation of Sorting Algorithms | All required sorts are implemented correctly: Bubble, Selection, Insertion, Shell, Merge, and the three Quick Sort variants. Arrays are properly reset before each run and results are correctly sorted. | 35 | |
| Performance Measurement & Comparison Counting | CPU time is measured correctly for each algorithm using the provided timing function (or equivalent). Number of comparisons is counted consistently and reported for all algorithms. | 20 | |
| Experimental Design & Test Coverage | Program runs the full experiment for all required array sizes (10k, 20k, 40k, 60k, 80k). Each algorithm is tested on identical data via saved copies. | 20 | |
| Output Quality & Reporting | Output is clearly formatted in tables and includes: sort type, first 20 elements of the sorted array, number of comparisons, and execution time. Output is easy to read and interpret. | 15 | |
| Code Organization & Submission Quality | Code is well-structured, readable, and commented. Sorting functions are stored in a list and iterated over. GitHub repository is complete and includes required output. | 10 | |
| Total | 100 |
Teams:
Lab10-Pair-01: Hoan Nguyen, Luke Galik
Lab10-Pair-02: Trang Nguyen, Davelle Ampofotwumasi
Lab10-Pair-03: Leo Xie, Shadia Amado-Aguad
Lab10-Pair-04: Joey (Jiayin) Liu, Cloris (Zongyu) Liu
Lab10-Pair-05: Calvin Deka, Nora Archer
Lab10-Pair-06: Khanh Mai, Moe Belghith
Lab10-Pair-07: Ella Rigoli, Westley (Kelly) Kailus
Lab10-Pair-08: Eden Cohen, Sariyah Sintayehu
Lab10-Pair-09: Peter Dunson, Djordje Dragojlovic
Lab10-Pair-10: Lucas Waite, Yaw Oppongkrampah
Lab10-Solo-11: Adam Khan
Lab10-Solo-12: Kuba Kopczuk