# [plt-scheme] Quicksort in Scheme

 From: Matthias Felleisen (matthias at ccs.neu.edu) Date: Wed Jan 4 14:01:11 EST 2006 Previous message: [plt-scheme] Quicksort in Scheme Next message: [plt-scheme] Re: Quicksort in Scheme Messages sorted by: [date] [thread] [subject] [author]

```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.
> _________________________________________________