a2

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
  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
  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
  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). 

Boilerplate

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.

Table of Grades

0
1
2
3
4
5
6
7 5 8
8 2 5 7
9 0 5 5
10 0
11 4

Comments and Clarifications


Questions? Answers!
Valid CSS! Valid XHTML 1.1!