SketchyLISP Stuff | Copyright (C) 2006 Nils M Holm |
[ More Sketchy LISP Stuff ] |
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)
[ More Sketchy LISP Stuff ] |