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 (list-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 (list-remove lst val)
  (if (eq? val (car lst))
      (cdr lst)
      (cons (car lst) (list-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 list-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))
> (list-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 1000))
(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. Although we normally use computer programs to help us understand data, we'll work on the board to visualize the data.

a. There should be a scale on the board. Plot your points.

b. Once everyone has plotted his or her points, we'll try to figure out the approximate shape of the curve.

c. How do we test our hypothesis about the shape of the curve?