qsort

Conformance: SketchyLISP Extension

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
    ((left-part
       (lambda (x)
         (lambda (y) (not (p x y)))))
     (right-part
       (lambda (x)
         (lambda (y) (p x y))))
     (_qsort
       (lambda (a)
         (cond ((null? a) a)
           (else (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)

See also:
ordered?.