So my point is, you know that it's evaluating (split pivot ...) twice because you have the same expression written twice in there.
So where you have
(list (quicksort (car (split pivot (cdr L) () ()))) pivot
(quicksort (cdr (split pivot (cdr L) () ())))))
you should write
(let ((x (split pivot (cdr L) () ())))
(list (quicksort (car x)) pivot (quicksort (cdr x))))
That way, you're only evaluating the split once.
So I would write, as a simple tweak of your version:
(define (split piv xs lessers greaters)
(cond ((null? xs) (cons lessers greaters))
((< (car xs) piv)
(split piv (cdr xs) (cons (car xs) lessers) greaters))
(else
(split piv (cdr xs) lessers (cons (car xs) greaters)))))
(define (bad-quicksort xs)
(if (null? xs)
'()
(let* ((pivot (car xs))
(splitted (split pivot (cdr xs) '() '())))
(append (bad-quicksort (car splitted))
(cons pivot (bad-quicksort (cdr splitted))))))) The reason I call it "bad" is that some improvement can be made. The bad thing about this quicksort implementation is that once the interior lists are sorted, they have to be appended together. This requires copying the list you've just built! So instead, I would recommend changing the question from "sorting a list" to "sorting a list and appending it onto another list".
(define (quicksort-onto xs onto)
(if (null? xs)
onto
(let* ((pivot (car xs))
(splitted (split pivot (cdr xs) '() '())))
(quicksort-onto (car splitted)
(cons pivot (quicksort-onto (cdr splitted)
onto))))))
(define (quicksort-calls-onto xs)
(quicksort-onto xs '())) In terms of algorithm design, if we disallow destructive operations, this seems the best we can get. But the implementation can be better by using a named let macro.
(define (quicksort-decent xs)
(let sort ((xs xs) (onto '()))
(if (null? xs)
onto
(let* ((pivot (car xs))
(splitted (split pivot (cdr xs) '() '())))
(sort (car splitted)
(cons pivot (sort (cdr splitted)
onto))))))) The code
(let f ((arg1 val1) ...) <body>) is equivalent to
(letrec ((f (lambda (arg1 ...) <body>))) (f val1 ...)) and it's handy for writing tail-recursive loops. But you can also use it for general recursive functions, like we did above.
Now, that's still kind of ugly, because we rely on the ugly
split function. To avoid that, we can use the function
filter from the SFRI-1 library.
(define (quicksort-filter xs)
(let sort ((xs xs) (onto '()))
(if (null? xs)
onto
(let ((pivot (car xs)))
(sort (filter (lambda (x) (< x pivot)) (cdr xs))
(cons pivot
(sort (filter (lambda (x) (<= pivot x)) (cdr xs))
onto))))))) Which cleans up our code quite a bit. But even better, SFRI-1 has a function called
partition that pretty much does what our split function does! The thing is,
partition returns multiple values... but not in a cons cell. It returns multiple values
directly, using some crazy feature that Scheme has for some reason.
If a procedure returns more than one value, you can't assign it to something like you do with
let . (At least not without SFRI-8, but we'll get to that.) Instead, you have to use the
call-with-values function. An example of usage:
(call-with-values
(lambda () (values 20 21)) ; returns two values, 20 and 21
(lambda (x y) (sqrt (+ (* x x) (* y y))))) ; receives 20 and 21 as arguments
With that in mind, we can write quicksort to use
partition :
(define (quicksort-call-with-values xs)
(let sort ((xs xs) (onto '()))
(if (null? xs)
onto
(let ((pivot (car xs)))
(call-with-values
(lambda ()
(partition (lambda (x) (< x pivot)) (cdr xs)))
(lambda (fore aft)
(sort fore (cons pivot (sort aft onto))))))))) Ugly! Fortunately, the Scheme extension SFRI-8 provides a macro, much like
let , that makes using
functions that return multiple values a bit easier.
(define (quicksort-receive xs)
(let sort ((xs xs) (onto '()))
(if (null? xs)
onto
(let ((pivot (car xs)))
(receive (fore aft) (partition (lambda (x) (< x pivot)) (cdr xs))
(sort fore (cons pivot (sort aft onto)))))))) We can also write a destructive quicksort implementation simply by using the destructive version of partition.
(define (quicksort! xs)
(let sort ((xs xs) (onto '()))
(if (null? xs)
onto
(let ((pivot (car xs)))
(receive (fore aft) (partition! (lambda (x) (< x pivot)) (cdr xs))
(sort fore (cons pivot (sort aft onto)))))))) Since destructive partitioning can be done without burning through a bunch of memory allocations, maybe it's faster. So that gives us a non-destructive quicksort function:
(define (quicksort xs)
(quicksort! (list-copy xs)))
Marked Solved 
Offline 
