;; 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-intermediate-lambda-reader.ss" "lang")((modname quick-sort) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f () #f)))
; A PivotTree is one of
; - (make-no-pivot)
; - (make-pivot PivotTree Number PivotTree)
(define-struct no-pivot [])
(define-struct pivot [left val right])
; flatten : PivotTree -> [ListOf Number]
; read off a sorted list from the tree
(define (flatten pt)
(cond [(no-pivot? pt) empty]
[else (append (flatten (pivot-left pt))
(list (pivot-val pt))
(flatten (pivot-right pt)))]))
(check-expect (flatten (make-no-pivot)) empty)
(check-expect (flatten (make-pivot (make-no-pivot) 5 (make-pivot (make-no-pivot)
8
(make-no-pivot))))
(list 5 8))
; smaller : Number [ListOf Number] -> [ListOf Number]
; select the numbers less than or equal to n
(define (smaller n lon)
(cond [(empty? lon) empty]
[else (cond [(<= (first lon) n)
(cons (first lon) (smaller n (rest lon)))]
[else (smaller n (rest lon))])]))
(check-expect (smaller 5 (list 1 2 5)) (list 1 2 5))
(check-expect (smaller 3 (list 1 2 5)) (list 1 2))
(check-expect (smaller 3 empty) empty)
; build-pivot-tree : [ListOf Number] -> PivotTree
; split up a list of numbers into a pivot tree
; termination: smaller and larger are applied to the rest
(define (build-pivot-tree lon)
(cond [(empty? lon) (make-no-pivot)]
[else (make-pivot
(build-pivot-tree (smaller (first lon) (rest lon)))
(first lon)
(build-pivot-tree (larger (first lon) (rest lon))))]))
(check-expect (build-pivot-tree empty) (make-no-pivot))
(check-expect (build-pivot-tree (list 2 1 4))
(make-pivot (make-pivot (make-no-pivot) 1 (make-no-pivot))
2
(make-pivot (make-no-pivot) 4 (make-no-pivot))))
; quick-sort : [ListOf Number] -> [ListOf Number]
; sort the list using pivot trees
(define (quick-sort lon) (flatten (build-pivot-tree lon)))
(check-expect (quick-sort (list 2 1 4)) (list 1 2 4))