- Assigned
- Wednesday, Dec 5, 2018
- Due
- Lab writeups are due at 10:30pm on the day of the next class meeting. For example, a Wednesday lab is due at 10:30pm on Friday. Each lab writeup will be announced at the end of class on a lab day.
- Summary
- In this lab, we explore a variety of issues related to the insertion sort algorithm.

a. Update the `csc151`

package.

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<=?`

and `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
the generalized `insert`

procedure in writing `insert-string`

.

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-new`

, `counter-increment!`

, `counter-reset!`

,
and `counter-print`

are in the new `csc151/counters`

package.
Remind yourself of what they do.

b. Define a counter named `insert-number-counter`

.

```
(define insert-number-counter (counter-new "insert-number"))
```

c. Add the following line to the beginning of the `insert-number`

procedure.

```
(counter-increment! insert-number-counter)
```

We can count the number of calls to `insert-number`

for
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 `insert-number`

are
involved in sorting each of the following lists.

i. `(iota 5)`

ii. `(iota 10)`

iii. `(iota 20)`

iv. `(iota 40)`

v. `(reverse (iota 5))`

vi. `(reverse (iota 10))`

vii. `(reverse (iota 20))`

viii. `(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")`

alphabetically.

`insert!`

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 `numbers`

.

*Note:* Solving this step requires that you understand the parameters to
`vector-insert!`

.

c. Extend `vector-insert!`

so that it displays the vector and the
position at every step. That is, add calls to `display`

and `newline`

in the kernel, before the `cond`

.

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
`vector-insertion-sort!`

works.

a. You will note that the file for this lab includes a list called
`grinnell-directory`

. Review the structure of `grinnell-directory`

.
Then write a call to the generalized `list-keyed-insertion-sort`

to
sort by username.

b. Write a call to the generalized `list-keyed-insertion-sort`

to
sort the list ```
("clementine" "starfruit" "apple" "kumquat" "pineapple"
"pomegranate" "cantelope")
```

alphabetically. Note, for example, that
the key of `"clementine"`

is `"clementine"`

.

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
key of `("Rebelsky" "Essay" "muser" "4410")`

would be `"Rebelsky, Essay"`

.

Write a procedure, `(string-vector-insertion-sort vec)`

,
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 `vector-insertion-sort!`

appropriately.