[plt-scheme] HtDP 25.2.6

From: dave yrueta (dyrueta at gmail.com)
Date: Tue Mar 17 16:44:52 EDT 2009

Exercise 25.2.6 asks the student  to

"develop a variant of quick-sort that uses only one comparison
function, say, <. Its partitioning step divides the given list alon
into a list that contains the items of alon smaller than (first alon)
and another one with those that are not smaller."

Should this version of quick-sort eliminate the pivot item that
previous versions relied upon?  If not, is the version below

;qsort : (X X -> boolean) (listof X) -> listof X
;consumes a predicate and a listof X, returns a listof X sorted by the
;(check-expect (qsort < empty) empty)
;(check-expect (qsort > (list 1)) (list 1))
;(check-expect (qsort < (list 3 2 1)) (list 1 2 3))
;(check-expect (qsort > (list 1 2 3)) (list 3 2 1))
(define (qsort a-pred alon)
    [(empty? alon) empty]
    [(empty? (rest alon)) alon]
    [else (append (qsort a-pred (filter (lambda (x) (a-pred x (first
alon))) (rest alon)))
                  (list (first alon))
                  (qsort a-pred (filter (lambda (x) (not (a-pred x
(first alon)))) (rest alon))))]))

Dave Yrueta

Posted on the users mailing list.