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)

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

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