Copy the code from the accompanying reading into DrScheme.
Discuss with your partner (and perhaps a neighboring group) the significant differences between the list-based insertion sort described in the first part of the the reading and the insertion sort we discussed in class (and that appears in the second part of the reading). What is different other than that one deals with lists and the other with vectors?
a. Test both versions of the
insert-number procedure from the reading
by inserting a number
b. What happens if
ls is not in ascending order when
insert-number is invoked?
Write a new
string-insert procedure that inserts a string into a
list of strings that are in alphabetical order:
> (string-insert "dog" (list "ape" "bear" "cat" "emu" "frog")) ("ape" "bear" "cat" "dog" "emu" "frog")
a. Write a generalized
insert procedure that also takes a
less-than-or-equal-to predicate as a parameter.
b. Show how to call this procedure using lists of strings and numbers.
a. Add calls to the
to the body of the helper in
insertion-sort-numbers so that it displays the values of
sorted, appropriately labeled, at each
step of the sorting process.
b. Use the revised
procedure to sort the values 7, 6, 12, 4, 10, 8, 5, and 1.
insertion-sort-numbers procedure on some potentially
Write a procedure,
(insertion-sort list less-than-or-equal?).
that generalizes the
Write the generalized
insert! procedure that inserts a
value into a sorted vector that has "space" at a designated position.
Create and name a vector containing the strings
Rearrange the elements of the vector into alphabetical order by means of
an appropriate call to
insertion-sort!. (Note that the
sorting occurs as a side effect of this call. Hence, to confirm that
the sorting procedure worked you'll have to inspect the vector again
Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Labs/sorting.html
Source text last modified Fri Nov 17 22:06:20 2000.
This page generated on Fri Nov 17 22:09:27 2000 by Siteweaver. Validate this page's HTML.
Contact our webmaster at firstname.lastname@example.org