;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-beginner-abbr-reader.ss" "lang")((modname sort-example) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f () #f)))
; a list-of-num (lon) is either
; - '()
; - (cons num lon)
; lon -> ...
; template for a function that consumes a lon
;(define (fun-for-lon lon)
; (cond
; [(empty? lon) ...]
; [(cons? lon) ...(first lon)...
; ...(fun-for-lon (rest lon))...]))
; lon -> lon[sorted]
; sort numbers in given lon in ascending order
(define (sort-list lon)
(cond
[(empty? lon) '()]
[(cons? lon) (insert-list (first lon)
(sort-list (rest lon)))]))
(check-expect (sort-list '()) '())
(check-expect (sort-list (list 42)) (cons 42 '()))
(check-expect (sort-list (list 1 2 3))
(list 1 2 3))
(check-expect (sort-list (list 3 2 1))
(cons 1 (cons 2 (cons 3 '()))))
; num lon[sorted] -> lon[sorted]
; inserts n into sorted lon in its sorted position
(define (insert-list n lon)
(cond
[(empty? lon) (cons n '())]
[(cons? lon)
(cond
[(< n (first lon)) (cons n lon)]
[else (cons (first lon)
(insert-list n (rest lon)))])]))
(check-expect (insert-list 42 '()) (cons 42 '()))
(check-expect (insert-list 1 (cons 42 '()))
(cons 1 (cons 42 '())))
(check-expect (insert-list 42 (cons 1 '()))
(list 1 42))
(check-expect (insert-list 4 (list 1 2 3))
(list 1 2 3 4))
(check-expect (insert-list 0 (list 1 2 3))
(list 0 1 2 3))
(check-expect (insert-list 3 (list 1 2 4 5))
(list 1 2 3 4 5))