# [plt-scheme] Quicksort in Scheme

You're saving money at the wrong end. How would you like
(append
(qs (filter (lambda (x) (> x pivot)) l))
(list pivot)
(qs (filter (lambda (x) (< x pivot)) l)))
as the recursive step in qs? (Yeah yeah, I don't worry about duplicate
elements blah).
-- Matthias
On Jan 4, 2006, at 1:50 PM, Greg Woodhouse wrote:
>* 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
*>* order
*>*
*>>* (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.
*>* _________________________________________________
*>* For list-related administrative tasks:
*>* http://list.cs.brown.edu/mailman/listinfo/plt-scheme
*