Requirement
The purpose of this homework program report is to discuss, analyze and report “different” sorting algorithms and their complexities. You will run your program with different input sizes and average each of your results with ]10 runs for each input size.
You will need to submit a written report with part of your codes and your source code via Blackboard. You also need to bring in a hard copy of the report with part of your codes to the class on the day that this is due.
Each part needs to be their own functions.
Generate arrays of size 10^2, 10^4, and 10^6 of random integer. These arrays are the lists you are sorting.
Generate arrays of size 10^2, 10^4, and 10^6 of integer from 1 to n, where n is the size of the array.
Generate arrays of size 10^2, 10^4, and 10^6 of integer from n to 1, where n is the size of the array.
Implement the sorting. Do not use build in functions.
- a. Straight Insertion Sort
- b. Merge Sort
- c. Merge Sort in conjunction with Straight Insertion Sort when the sub-array has less than k keys, where k is the input size when Insertion Sort is better Merge Sort
- d. Quicksort
- e. Quicksort in conjunction with Straight Insertion Sort when the sub-array has less than k keys, where k is the input size when Insertion Sort is better Quicksort
- f. Heap Sort
Implement two counters to count the comparison and swap operation for each sort.
Step 2 and 3 are only required to do once.
Your report should consist of, but not limited to:
- how you generate the arrays
- how you implement the sorting algorithms
- the analysis of the sorting, big-oh.
- a table or graph or both of your results, how many comparisons, how many swaps.
- does your analysis match your results?
- your codes
Example structures of the report:
- How you generate the arrays for the lists
- Code for your generation of the arrays for the lists
- How you implement the Straight Insertion Sort and the analysis of your implementation
- Code for your implementation of the Straight Insertion Sort
- Other sorting algorithms
- Your experimental results, i.e. tables, graphs, etc
- Explain the similarities or differences of your analyses and your results.