Exercise: Studying Selection Sort

Here is the selection sort algorithm as implemented in Scheme. (Note that I've eliminated many of the comments that would typically accompany the program code.)

(define (selection-sort lst)
  (if (null? lst)
      null
      (selection-sort-helper (smallest lst) lst)))
  
  ; The helper procedure handles the deletion of the smallest
  ; element and the repetition
  (define (selection-sort-helper smallest-value lst)
     (cons smallest-value 
          (selection-sort (remove lst smallest-value))))

(define (smallest lst)
  (if (null? (cdr lst))
      (car lst)
      (smaller (car lst) (smallest (cdr lst)))))

(define (smaller val1 val2)
  (if (< val1 val2) val1 val2))

(define (remove lst val)
  (if (eq? val (car lst))
      (cdr lst)
      (cons (car lst) (remove (cdr lst) val))))

You can use these procedures by adding the following line to your definitions pane and then clicking execute.

(load "/home/rebelsky/Web/Scheme/simple-selection-sort.ss")

1. Test the three key helper procedures, smallest, smaller, and remove. Here are some examples to get you started.

> (smaller 1 2)
> (smaller 2 1)
> (smaller -5 2)
> (smallest (list 1 2 3 4 5))
> (remove 4 (list 1 2 3 4 5))

2. Test selection-sort on some simple lists you create yourself.

3. For more intersting testing, you need a way to create large lists. Here's a procedure I like to use.

(define (random-list n)
  (if (= n 0)
      null
      (cons (random 1000) (random-list (- n 1)))))

You can add this definition in your definitions window. I've also put a copy of this procedure in a file, which you can load with

(load "/home/rebelsky/Web/Scheme/random-list.ss")

Try creating random lists of 5, 10, and 100 elements.

4. You can now combine pieces to build and sort larger lists as a way of testing selection sort. Here are some examples:

> (define sample (random-list 500))
> (length sample)
500
> sample
(243
 590
 ...
 866)
> (selection-sort sample)
(0
 4
 5
 ...
 999
 999)
> (selection-sort (reverse (selection-sort sample)))
(0
 4
 5
 ...
 999
 999)

a. Try some of your own examples.

b. Why do you think I included that last test?

5. As we discussed, it is often useful to be able to predict the running time of an algorithm. We'll use an experimental approach. In your CS courses, you will also see a more formal approach. We need to begin by gathering information on the running time of selection sort on various sizes of inputs. Here's a technique I've found useful. Enter the following in your definitions window

(load "/home/rebelsky/Web/Scheme/simple-selection-sort.ss")
(load "/home/rebelsky/Web/Scheme/random-list.ss")
(define sample (random-list 100))
(define result null)
(time (set! result (selection-sort sample)))

Gather between ten and twenty data points for running time using different size lists.

6. Most of us can't see patterns in numeric data and instead rely on visualization techniques. We'll use a program called Maple to visualize these data.

a. You may have a Maple icon in your control panel. If so, click it. If not, click on the picture of the terminal with the foot and then type xmaple.

b. In the untitled window, enter the following, which provides some sample data

spoints := pointplot({[100,500],[200,1000]}
                     symbolsize=10,
                     color=blue,
                     view=[0..300,0..1100]):
sfun := plot(x*x/1000, x=1..1000, color=green):
display({spoints});

c. Past experience tells us that the values for selection sort follow a quadratic curve so we want to draw a parabola that matches. Update the display line to read

display({spoints,sfun});

d. Update the coefficient of x*x in the plot so that the curve matches your data. You may have to try a variety of values before you find a good match.