Homework 5
1. Implement the selection sort algorithm provided in the text and obtain empirical timing results for sorting random lists of integers. You should obtain data for 20 different list sizes. The data for each list size should be obtained by averaging the sort time for 3 random lists of the specified size. The largest list analyzed should take about 10 seconds to sort. Produce a graph of the results and comment on whether your data supports the theoretically expected values.
2. Modify the above sort to avoid performing a swap when the ith record is already in the correct location (i.e. you are avoiding swapping location i with location i). Do you expect that this will improve the sorting performance? Rerun your timing experiment on the same sample data as before (use the same random lists) and produce a graph that compares the two algorithms. Comment on the results of the experiment compared to your expectations.
Submit a printed copy of the program used in question 2 along with the report.
3. Implement the shell sort algorithm found in the text. Experiment to determine how large a list of integers you can sort within 10 seconds on your computer. Produce a table and graph of sorting times for about 20 lists (average the times for 3 lists of each size) up to that size. Report on the results.
Run the program CPUBench on the system used to do the sorting (this is a freeware application and simply calculates the speed of your processor using a few computational tests - unzip and run - no install needed) and report the three values it determines for your system. You should click the Exclusive System Priority item on the CPUBench menu to get the most accurate data.
Turn in a printed copy of your program along with the report.