[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