[plt-scheme] Quicksort in Scheme
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.