CSC 153: Computer Science Fundamentals | Grinnell College | Spring, 2005 |
Laboratory Exercise Reading | ||
This reading explores the insertion sort as a mechanism to order numbers on a 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.
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)))
)
)
)
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
created March 8, 1998 last revised February 3, 2005 |
![]() ![]() |
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. |