[plt-scheme] Quicksort in Scheme

 From: Greg Woodhouse (gregory.woodhouse at sbcglobal.net) Date: Wed Jan 4 13:50:41 EST 2006 Previous message: [plt-scheme] planet down? Next message: [plt-scheme] Quicksort in Scheme Messages sorted by: [date] [thread] [subject] [author]

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

```

 Posted on the users mailing list. Previous message: [plt-scheme] planet down? Next message: [plt-scheme] Quicksort in Scheme Messages sorted by: [date] [thread] [subject] [author]