Due 5pm Friday June 24
For this assignment you will need to write quicksort, quickselect, and linear time select. For extra credit, when your file is run directly from the command line (and only then) you should make it print out its own source code without using file I/O. This initially seems like quite a lot of work, but if you remember that these algorithms share quite a bit of code, then you should have to write under 100 lines to get this all done. The source code printer will probably about double that, but most of that increase will be multiline strings.
quickselect(a,k) -> the kth element of a if a were sorted Given an unsorted array a, return what would be element k if the array were sorted. This one only has to be expected O(N).
quicksort(a) -> array a in sorted order Given an array a, return that array in sorted order. You don't have to modify it in place if you don't want to. Just return an array containing the same elements as a, but in sorted order.
select(a,k) -> the kth element of a if a were sorted Given an unsorted array a, return what would be element k if the array were sorted. This one has to be guaranteed O(N).
Ask me if there are any questions, and remember that elegance counts! peter@cs.uoregon.edu, or simply commenting below will all reach me immediately. Also recommended is coming in to office hours if you have any questions.
0 | |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | 5 8 |
8 | 2 5 7 |
9 | 0 5 5 |
10 | 0 |
11 | 4 |
Questions? Answers!