# Insertion Sort

Summary: In this lab, we explore a variety of issues related to the insertion sort algorithm.

## Preparation

a. Make a copy of `insertion-sort-lab.scm`, the code for this lab.

b. In that file is the definition of a list named `drawing`. Look at that definition and do your best to understand the form of the list.

## Exercises

### Exercise 1: Testing Insert

a. Test the `insert-number` procedure from the reading by inserting the number 42

• into an empty list;
• into a list of numbers larger than 42, arranged in ascending order;
• into a list of numbers smaller than 42, arranged in ascending order;
• into a list of numbers both smaller and larger than 42, arranged in ascending order; and
• into a list that contains only three copies of 42 (that is, the list created by `(list 42 42 42)`.

b. Discuss with your partner (or someone nearby) why you think we had you do each of these tests. (That is, why would one want to check that `insert-number` works on each of these lists?)

c. What would you expect to happen if the list is not in ascending order when `insert-number` is invoked?

### Exercise 2: Inserting Strings

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

### Exercise 3: Displaying Steps in Insertion Sort

a. Add calls to the `display` and `newline` procedures to the body of the helper in `numbers-insertion-sort` so that it displays the values of `unsorted` and `sorted`, appropriately labeled, at each step of the sorting process.

b. Use the revised `numbers-insertion-sort` procedure to sort the values 7, 6, 12, 4, 10, 8, 5, and 1.

### Exercise 4: Checking Potential Problems

When we use a new procedure, we often want to test it on a variety of cases. We've seen that `numbers-insertion-sort` works on a few simple cases. But we should also check some “special cases”, cases that might stress the algorithm. Make a list of some lists that a poorly-implemented insertion sort procedure might have difficulty with.

### Exercise 5: Checking Potential Problems, Revisited

Review the code for `numbers-insertion-sort` to figure out what you think it will do for each of the following cases. Then check your answer experimentally.

a. An empty list.

b. A list containing only one element.

c. A list containing all equal values.

d. A list in which the elements are originally in descending numerical order.

e. A list in which the elements are already in ascending numerical order.

f. A list containing some duplicate elements.

### Exercise 6: Counting Steps in Insertion Sort

a. Using `define\$` (for both `insert-number` and `numbers-insertion-sort`) and `analyze`, determine how many calls to `insert-number` are involved in sorting each of the following lists. For example, for the first list, you would write

````>` `(analyze (numbers-insertion-sort (iota 5)) insert-number)`
```

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

b. Explain, to the best of your ability, what the numbers you got say about the number of steps insertion-sort takes.

### Exercise 7: Generalized Insertion Sort

Write a call to the generalized `list-insertion-sort` to sort the list ```("clementine" "starfruit" "apple" "kumquat" "pineapple" "pomegranate")``` alphabetically.

### Exercise 8: Observing `insert!`

```(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 this procedure works.

## For those with Extra Time

### Extra 1: Keyed Insertion Sort

a. Write a call to the generalized `list-keyed-insertion-sort` to sort the list ```("clementine" "starfruit" "apple" "kumquat" "pineapple" "pomegranate")``` alphabetically.

b. Review the structure of `drawing` (a list of named objects). Then write a call to the generalized `list-keyed-insertion-sort` to sort `drawing` by object name.

c. Write a call to the generalized `list-insertion-sort` to sort `drawing` alphabetically by color name.

d. Write a call to the generalized `list-keyed-insertion-sort` to sort drawing by object width.

### Extra 2: Keyed Insertion Sort for Vectors

Write a procedure, ```(vector-keyed-insertion-sort vec get-key may-precede?)``` that sorts a vector of compound objects 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 directly. (You may want to use `vector-insertion-sort!` as a template.)

Copyright (c) 2007-9 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.)

This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. To view a copy of this license, visit `http://creativecommons.org/licenses/by-nc/2.5/` or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.