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

# Sorting

## Abstract

This reading explores the insertion sort as a mechanism to order numbers on a list.

## Maintaining An Ordered List

Many applications require the maintenance of ordered data. In Scheme, the simplest way to structure ordered data is in a list, such as the following ordered list of integers:

``````
(2 3 5 7 9 10 13 18 24)
``````
Given such a list, two common operations involve inserting an item into the list or removing an item from the list.

### Insertion into an Ordered List:

The following code 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)))
)
)
)
``````

## Insertion Sort

One approach to sort a list incorporates the above insertion process. In particular, a new list is built up -- starting with the null list and inserting one item at a time. The specific code follows:

``````
(define insertion-sort
(lambda (ls)
(if (null? ls)
ls
(insert-item (car ls) (insertion-sort (cdr ls)))
)
)
)
``````

While the above code performs sorting using two separate procedures, `insert-item` and `insertion-sort`, the work could be defined in 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)))
)
)
)
)
``````

This document is available on the World Wide Web as

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