a. Update the
b. Make a copy of insertion-sort-lab.rkt, the code for this lab.
c. With your partner, review your answers to the self checks from the corresponding reading.
Write a new
insert-string procedure that inserts a string into a list
of strings that are in alphabetical order.
> (insert-string (list "ape" "bear" "cat" "emu" "frog") "dog")` ("ape" "bear" "cat" "dog" "emu" "frog")
In case you’ve forgotten,
string-ci<=? are useful
predicates for comparing strings for order.
Your goal in this problem is to follow (and therefore better understand)
the pattern of the
insert-number procedure. Hence, you may not use
insert procedure in writing
Let’s see how many times the
insert-number method is called. We’ll use
the techniques from the lab on analyzing procedures.
a. The procedures
counter-print are in the new
Remind yourself of what they do.
b. Define a counter named
(define insert-number-counter (counter-new "insert-number"))
c. Add the following line to the beginning of the
We can count the number of calls to
a particular list as follows:
> (counter-reset! insert-number-counter) > (numbers-insertion-sort *list*) > (counter-print insert-number-counter)
d. Determine how many calls to
involved in sorting each of the following lists.
(reverse (iota 5))
(reverse (iota 10))
(reverse (iota 20))
(reverse (iota 40))
e. Explain, to the best of your ability, what the numbers you got say about the number of function calls the insertion sort algorithm makes. Your answer should take the length of the list into account.
Write a call to the generalized
list-insertion-sort to sort the list
("clementine" "starfruit" "apple" "kumquat" "pineapple" "pomegranate")
a. Add the following definition to your definitions pane.
(define numbers (vector 1 5 6 7 2 8 0 3))
b. Check that
vector-insert! works by using it to move the 2 into the
correct place in the first five spaces in
Note: Solving this step requires that you understand the parameters to
vector-insert! so that it displays the vector and the
position at every step. That is, add calls to
in the kernel, before the
d. Re-create the
numbers vector from step a, and observe what happens
when we insert the 2, then the 8, then the 0, then the 3.
e. Observe the insertion steps in a vector of about eight randomly-generated numbers.
> (define nums (vector (random 10) (random 10) (random 10) (random 10) (random 10) (random 10) (random 10) (random 10))) > (vector-insertion-sort! nums _____)
f. Explain, in your own words, how
a. You will note that the file for this lab includes a list called
grinnell-directory. Review the structure of
Then write a call to the generalized
sort by username.
b. Write a call to the generalized
sort the list
("clementine" "starfruit" "apple" "kumquat" "pineapple"
"pomegranate" "cantelope") alphabetically. Note, for example, that
the key of
c. Write a call to the generalized
list-keyed-insertion-sort to sort
alphabetically by last name and first name. Note, for example, that the
("Rebelsky" "Essay" "muser" "4410") would be
Write a procedure,
that sorts a vector of strings. You may not call the generalized
vector-insertion-sort. However, you may use that procedure
(and the corresponding generalized
vector-insert!) as a template
for your procedure.
Write a procedure,
(vector-keyed-insertion-sort vec get-key
may-precede?), that sorts a vector of lists by key.
While it is possible to write this procedure by converting the vector
to a list, using
list-keyed-insertion-sort!, and then converting the
result back to a vector, you should not use this strategy. Rather, write
this procedure so that it calls