...
in your program. As a rough guideline follow the https:wikiriceedudisplayCSWIKI211lab04parsess parse.ssâss program that we wrote in class on Monday, Feb 2. Note that finding the first input is more involved than finding the first line. You will probably want to explicitly check for errors in the input because they correspond to natural tests on the form of the input.
...
Code Block |
---|
;; insertion sort (define (isort alon) (cond [(empty? alon) empty] [(cons? alon) (insert (first alon) (isort (rest alon)))])) (define (insert new sortedlon) (cond [(empty? sortedlon) (list new)] [else (if (< new (first sortedlon)) (cons new sortedlon)] (cons (first sortedlon) (insert new (rest sortedlon))))])) ;; quicksort (adapted to functional lists) (define (qsort alon) (cond [(empty? alon) empty] [(cons? alon) (local [(define pivot (first alon)) (define other (rest alon)) (define lesser (filter (lambda (n) (<= n pivot)) other)) (define greater (filter (lambda (n) (> n pivot)) other))] (append (qsort lesser) (list pivot) (qsort greater)))])) |
...
- We need some data to use for our timing experiments. Write a function
up: nat -> (list-of nat)
which constructs a list of naturals starting with0
in ascending order or retrieve it from a previous lab. For example,(up 7)
returns(list 0 1 2 3 4 5 6)
. You can probably write it faster usingbuild-list
that you can retrieve it. Similarly, write a functiondown: nat -> (list-of nat)
that constructs a list of naturals ending in0
in descending order. For example,(nums-down 7)
returns(list 6 5 4 3 2 1 0)
. - Now write a function
that constructs a list of random numbers in the range from {{Code Block unmigrated-wiki-markuprands
0
}} to {{32767
}}. To create a single random number in the range from {{0
}} to {{{_}n
{_}}}, compute {{(random
_n+1
_)
}}. For larger numbers in the range {{\[0,
32768)
}}, try:
Note:Code Block (define max-rand 32768) (random max-rand) ; random is built-in
random
is a function in the Scheme library, but it is not a mathematical function, since the output is not determined by the input. - Make sure you know how to use
time
by using it to timeisort
on a list of 200 elements. Run the exact same expression again a couple times. Note that the time varies some. We typically deal with such variation by taking the average of several runs. The variation is caused by a number of low-level hardware phenomena that are beyond the scope of this course (see ELEC 220 and COMP 221). - Use the
time
operation to fill in the following chart.When you are done, compare your results with those generated by other pairs in the lab.input size
input size
input size
200
1000
5000
up
isort
down
rand
up
qsort
down
rand
...