[plt-scheme] Quicksort in Scheme

From: Greg Woodhouse (gregory.woodhouse at sbcglobal.net)
Date: Wed Jan 4 13:50:41 EST 2006

Tired of hearing from me yet? I decided to try my hand at implementing
Quicksort in Scheme, but there's a problem with what I have so far:

;;This function just generates a (pseudo-random) list
;;for test purposes.
(define random-list
  (lambda (size range)
    (if (> size 0)
        (cons (random range) 
              (random-list (- size 1) range))

;;This function takes a number (pivot) and a list,
;;returning two list: values <= the pivot, and 
;;values > the pivot.
(define partition
  (lambda (p l)
    (let loop
      ((pivot p)
       (numbers l)
       (small '())
       (large '()))
      (if (null? numbers) (list small large)
          (if (> p (car numbers))
              (loop p (cdr numbers)
                    (cons (car numbers) small) large)
              (loop p (cdr numbers)
                    small (cons (car numbers) large)))))))

namely, the partition function creates sublists sorted in the wrong

> (partition 3 '(1 2 3 3 4 5 5 6))
((2 1) (6 5 5 4 3 3))

I suppose I could use append, but doesn't that imply traversing the
entire list for each element (giving me a quadratic sort)?

Gregory Woodhouse  <gregory.woodhouse at sbcglobal.net>
"If you give someone Fortran, he has Fortran.
If you give someone Lisp, he has any language he pleases."
--Guy L. Steele, Jr. 

Posted on the users mailing list.