(Nils' Scheme Snippets)

Paren matching: OFF | Category: lists | Overview | Scheme Books | License

(qsort proc² list) => list

Purpose

Sort lists using the quicksort algorithm. The predicate p desribes the desired order.

Arguments

p	predicate
a	list

Dependencies

partition

Example

(qsort < '(5 3 7 9 1)) => (1 3 5 7 9)

(load "partition.scm")

(define (qsort p a)
  (letrec
    ((sort
       (lambda (a)
         (if (null? a)
             a
             (let ((p* (partition (lambda (x) (p (car a) x))
                                  (cdr a))))
               (append (sort (cadr p*))
                       (list (car a))
                       (sort (car p*))))))))
    (sort a)))

(Nils' Scheme Snippets)

(qsort proc2 list) => list

(qsort proc² list) => list