Selection sort is not the only well-know sorting algorithm. Other common ones include insertion sort and merge sort. Which is best? Let's try to figure out experimentally (a) how each does on a variety of different kinds of inputs and (b) what the approximate curve is for the running time of each.
You can load an implementation of selection sort with
(load "/home/rebelsky/Web/Scheme/simple-selection-sort.ss")That Scheme file provides the procedures
(remove val lst)
You can load an implementation of insertion sort with
(load "/home/rebelsky/Web/Scheme/simple-insertion-sort.ss")That Scheme file provides the procedures
(insert val lst)
You can load an implementation of merge sort with
(load "/home/rebelsky/Web/Scheme/simple-merge-sort.ss")That Scheme file provides the procedures
(merge slst1 slst2)
Using the techniques you've developed for evaluating the running time of selection sort, compare the running times of selection sort, insertion sort, and merge sort. Which is fastest on large problems? On small? How much faster? Does it matter if we start with a sorted list? With a reverse-sorted list?
Note that you may have difficulty finding a quadratic function that matches the running time of merge sort. You might want to try other functions to see if you can get a better fit.
This document was generated by
Siteweaver on Tue Aug 17 07:43:10 2010.
The source to the document was last modified on Tue Aug 17 07:41:45 2010.
This document may be found at