t3x.org / sketchy / prog / qsort.html
SketchyLISP Stuff Copyright (C) 2006 Nils M Holm

qsort

Conformance: R5RS

Purpose: Sort a list using the Quicksort algorithm.

Arguments:
A - list to sort
P - predicate defining the desired order

Implementation:

(define (qsort p a)
  (letrec

    ((filter (lambda (p a r)
      (cond ((null? a) (reverse r))
        ((p (car a))
          (filter p (cdr a) (cons (car a) r)))
        (#t (filter p (cdr a) r)))))
    (_qsort (lambda (a)
      (cond ((null? a) a)
        (#t (letrec
              ((left-part (lambda (x)
                (lambda (y) (not (p x y)))))
              (right-part (lambda (x)
                (lambda (y) (p x y)))))
              (append
                (_qsort (filter
                          (left-part (car a))
                          (cdr a) '()))
                (list (car a))
                (_qsort (filter
                          (right-part (car a))
                          (cdr a) '())))))))))
    (_qsort a)))

Example:

(qsort < '(5 1 3 2 4)) 
=> (1 2 3 4 5)