Sorting a list of numbers:
Selection Sort
Goal
Sort a list of value in increasing order Idea
Find the minimum,
Extract it (remove it from the list), Sort the remaining elements,
Add the minimum back in front!
✤
✤
✤
✤
✤
✤
✤
Putting the pieces together to sort
Use smallest and remove!
(define (selSort l)
(if (null? l)
‘()
(let* ((first (smallest l))
(rest (remove first l)))
(cons first (selSort rest)))))
✤
✤
✤
✤
To first bind first to the smallest element of the list; Then use first’s value to trim the list.
Use a let*
And…to minimize clutter
(define (selSort l)
(define (smallest l)
(define (smaller a b) (if (< a b) a b))
(if (null? (cdr l))
(car l)
(smaller (car l) (smallest (cdr l)))))
(define (remove v l)
(if (null? l)
l
(if (equal? v (car l))
(cdr l)
(cons (car l) (remove v (cdr l))))))
(if (null? l)
'()
(let* ((first (smallest l))
(rest (remove first l)))
(cons first (selSort r)))))
No need to traverse the list twice; one pass extraction & minimization
Goal
Find and Extract the smallest element from a list (in one pass!). Idea
Return two things (a pair!)
The extracted element
The list without the extracted element.
✤
✤
✤
✤
✤
✤
Minimization and Extraction in One Sweep
To improve readability, we introduce convenience functions to make & consult pairs.
Reserve cons/car/cdr for list operations
(define (make-pair a b) (cons a b))
(define (first p) (car p))
(define (second p) (cdr p))
(define (extractSmallest l)
(if (null? (cdr l))
(make-pair (car l) '())
(let ((p (extractSmallest (cdr l))))
(if (< (car l) (first p))
(make-pair (car l) (cons (first p) (second p)))
(make-pair (first p) (cons (car l) (second p)))
))))
✤
✤
Assume l has at least one element
The Picture
l
extractSmallest (.)
?
Reassemble, depending on which is smaller...
Then Selection Sort is easy...
Use the combined find and extract
(define (selSort l)
(if (null? l)
'()
(let ((p (extractSmallest l)))
(cons (first p) (selSort (second p))))))
✤
✤
✤
✤
extractSmallest returns a pair
Pick the first as the value to place in front
Pick the second as the trimmed list to recur on.
Accumulators
We’ve seen some example of computing in Scheme with “accumulators.” This is a particular way to organize Scheme programs that can be useful.
The idea: Recursive calls are asked to return the FULL value of the whole computation, you pass some PARTIAL results down to the calls.
✤
✤
(define (sort unexamined sorted)
...)
Already sorted elements
Elements needing to be handled
A Solution using Accumulators
(define (alt-extract elements)
(define (extract-acc smallest dirty clean)
(cond ((null? dirty) (make-pair smallest clean))
((< smallest (car dirty)) (extract-acc smallest
(else (extract-acc (car dirty)
(cdr dirty)
(cons smallest clean)))))
(extract-acc (car elements) (cdr elements) '()))
(cdr dirty)
(cons (car dirty)
clean)))
Smallest so far
Unexamined elts Examined elts
What’s the difference?
✤
✤
✤
✤
In our original solution, “partial problems” are passed as parameters; “partial solutions” are passed back as values.
In our accumulator solution, “partial solutions” are passed as parameters; complete solutions are passed back as values.
Trace a short evaluation!
Both of these are good techniques to keep in mind; some problems can be more elegantly factored one way or the other.
What about another ordering?
For instance....
Get the sorted list in decreasing order! Wish
Do not duplicate all the code.
✤
✤
✤
✤
Idea
Externalize the ordering!
Pass a function that embodies the order we wish to use.
✤
✤
Examples
(selSort
(selSort
✤
(lambda (a b) (< a b))
(list 3 6 1 0 7 4 2 8 9 5 12))
(lambda (a b) (> a b))
(list 3 6 1 0 7 4 2 8 9 5 12))
Output:
(0 1 2 3 4 5 6 7 8 9 12) (12 9 8 7 6 5 4 3 2 1 0)
Selection Sort with an Externalized Ordering
(define (selSort before? l)
(define (smallest l)
(define (smaller a b) (if (before? a b) a b))
(if (null? (cdr l))
(car l)
(smaller (car l) (smallest (cdr l)))))
(define (remove v l)
(if (null? l)
l
That’s it! No other changes needed!
(if (equal? v (car l))
(cdr l)
(cons (car l) (remove v (cdr l))))))
(if (null? l)
‘() How does this work?
(let* ((f (smallest l))
(r (remove f l)))
(cons f (selSort r)))))
Yet…. before is used from smaller not from selSort.
Closure
It’s all about the environments!
When entering selSort, the environment has a binding for before?
When defining smallest, scheme uses the current environment
Therefore before? is still in the environment.
When defining smaller scheme evaluates before? and picks up
its definition from the current environment!
The definition of smaller has captured a reference to before?
✤
✤
✤
✤
✤
Let’s QuickSort
Algorithm design idea
Divide and Conquer!
sort! sort!
✤
✤
7
2
9
11
1
14
8
0
3
12
6
10
5
2
1
0
3
6
5
9
11
14
8
12
10
0
1
2
3
5
6
8
9
10
11
12
14
0
1
2
3
5
6
8
9
10
11
12
14
combine
7
Key Ingredients
✤
✤
✤ ✤
✤
✤
✤ ✤ ✤
Partitioning
Use a pivoting element
Throw the smaller than pivot on left
Throw larger than pivot on right Sorting
Pick a pivot
Partition
Sort partitions recursively (What is the base case?) Combine answers
Partitioning
Why are we using accumulators for left/right?
✤
✤
✤ ✤
Base case:
Induction:
Returns:
empty list
Deal with one element from the list
a pair (the two partitions)
Recursive definition
(define (partition l pivot left right)
(cond ((null? l) (make-pair left right))
((< (car l) pivot) (partition (cdr l) pivot
(cons (car l) left)
right))
(else (partition (cdr l)
pivot left
(cons (car l) right)))))
QuickSort
Also Recursive
Base case: empty list
Induction: partition & sort
(define (qSort l)
(if (null? l)
l
(let* ((pivot (car l))
(parts (partition (cdr l) pivot '() '())) (left (qSort (first parts)))
(right (qSort (second parts))))
(append left (cons pivot right)))))
✤
✤
✤
Why are we using let* ?
Cleanup
✤
✤
✤
✤
✤
Once again, you can hide partition inside quickSort
After all, it is used only by quickSort.... Once again, you can externalize the ordering
Use a function for comparisons. Pass it down to quickSort!