;; Template:
;; (sort lon) sorts the elements of lon in non-decreasing order
(check-expect (sort (cons 2 (cons 0 (cons 1 empty)))) ...)
;; sort: (listof Num) -> (listof Num)
(define (sort lon)
(cond [(empty? lon) ...]
[else (... (first lon)
(sort (rest lon)) ...)]))
;; Fill in:
(define (sort lon)
(cond [(empty? lon) empty]
[else (insert (first lon)
(sort (rest lon)))]))
;; (insert n slon) inserts the number n into the sorted list slon...
;; insert: Num (listof Num) -> (listof Num)
;; requires: slon is sorted in non-decreasing order
(define (insert n slon)
(cond [(empty? slon) (cons n empty)]
[(<= n (first slon)) (cons n slon)]
[else (cons (first slon) (insert n (rest slon)))]))
(Note: This is known as insert sort!)
Condensed trace of sort and insert
(sort (cons 2 (cons 4 (cons 3 empty))))
⇒ (insert 2 (sort (cons 4 (cons 3 empty))))
⇒ (insert 2 (insert 4 (sort (cons 3 empty))))
⇒ (insert 2 (insert 4 (insert 3 (sort empty))))
⇒ (insert 2 (insert 4 (insert 3 empty)))
⇒ (insert 2 (insert 4 (cons 3 empty)))
⇒ (insert 2 (cons 3 (cons 4 empty)))
⇒ (cons 2 (cons 3 (cons 4 empty)))
Cons vs. list
| Cons | List |
|---|---|
| Consumes exactly two arguments: an Any and a list (may be empty) | Consumes any number of arguments and create a list exactly that length |
| Used to add one more item to the front of a list of arbitrary size. | Used to construct a list that has fixed size |
| List constructed with cons will explicitly show empty | List constructed with list will not explicitly show empty |
