[plt-scheme] HtDP 25.2.6
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
acceptable?
;qsort : (X X -> boolean) (listof X) -> listof X
;consumes a predicate and a listof X, returns a listof X sorted by the
predicate
;(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)
(cond
[(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))))]))
Thanks!
Dave Yrueta