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:

4. 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)))
      )
   )
)

5. 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))
   

6. Trace the working of insertion-sort by changing the define to trace-define.

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

8. Explain how this procedure works, including the use of the letrec statement.

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

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