Homework7: Sorting
Due: In class on Tuesday, March 25, 2008
Presentation By: Emily & Simona
Implement the Selection Sort (any version) Insertion Sort (version isort3 from page 116 of Bentley) and Quicksort algorithms (version qsort1 from page 119 of Bentley). Your implementation should be done using the following function headers:
selSort(A, n): Sorts an array/list A of n elements in ascending order
isort3(A, n): Sorts an array/list A of n elements in ascending order
qsort(A, n): Sorts an array/list A of n elements in ascending order.
You may write these programs in any language of your choice but use the same language for all implementations for comparison purposes.
Time the performance of your sort function (only) to sort arrays of sizes 100k, 500k, 1m, 2m, 3m, 5m, and 10m elements. Compare the results obtained for the three algorithms.
What to hand in:
1. A printout of your sorting functions (only). Please do not print anything else, just the sorting functions.
2. A table showing the time taken to sort arrays of the sizes shown above.
3. A plot showing the data from 2.
Please ensure that these are nicely formatted and in readable form.
Emily & Simona will give presentations on this project.