CSC 153 Grinnell College Spring, 2005 Computer Science Fundamentals Laboratory Exercise

# Sorting

## Goals

This laboratory exercise provides practice in defining and using the insertion sort as a mechanism to order numbers on a list.

## Maintaining An Ordered List

Consider the following code that inserts an item into an ordered list, ensuring that the new list remains ordered:

``````
;;; procedure to insert an item into a list, where elements are in
;;; ascending order
(define insert-item
(lambda (item ls)
(if (or (null? ls) (<= item (car ls)))
(cons item ls)
(cons (car ls) (insert-item item (cdr ls)))
)
)
)
``````
1. Check that `insert-item` works correctly in inserting the numbers 1, 9, 11 and 30 into the list ```(2 3 5 7 9 10 13 18 24) ```.

2. Rewrite `insert-item`, so that the body contains a named-let expression that performs the above work using tail recursion.

3. What happens if the list parameter for `insert-item` is not already ordered? For example, what happens if 6 is inserted into the list `(9 7 5 3 1)`?

#### Deletion from a List:

1. Write a procedure `delete-item` which removes one copy of a designated item from an ordered list. If the item is not present on the list, return an error. In your code, use the ordering of the list to minimize the amount of searching through the list.

### Insertion Sort

The following procedure uses the insert-item to successively build up an ordered list of values.

``````
(define insertion-sort
(lambda (ls)
(if (null? ls)
ls
(insert-item (car ls) (insertion-sort (cdr ls)))
)
)
)
``````
1. Check that this procedure works correctly by trying the following examples:
``````
(insertion-sort '(3 1 4 1 5 9 2 6 5 3 5))
(insertion-sort '(2 3 5 7 9 10 13 18 24))
(insertion-sort '(24 18 13 10 9 7 5 3 2))
``````
2. Trace the working of `insertion-sort` by changing the `define` to `trace-define`.

3. Write a few sentences explaining how this code works.

The following procedure combines the procedures, `insert-item` and `insertion-sort`, witin a single procedure:

``````
(define sort-ascending
(lambda (ls)
(letrec ((insert-item (lambda (item ls)
(if (or (null? ls) (<= item (car ls)))
(cons item ls)
(cons (car ls) (insert-item item (cdr ls)))))))
(if (null? ls)
ls
(insert-item (car ls) (sort-ascending (cdr ls)))
)
)
)
)
``````
1. Explain how this procedure works, including the use of the `letrec` statement.

2. Modify `sort-ascending`, so that the list is sorted in descending order rather than ascending order.

Work to be turned in:
• Observations, comments, and descriptions for parts 3, 7, and 8 of this section of the lab.
• Code (with test runs) for parts 2, 4, and 9.

This document is available on the World Wide Web as

```http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-insertion-sort.shtml
```

 created March 8, 1998 last revised February 3, 2005  For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.