sortingscheme

How do I get the partition to return two list output when pivot and the list are given as inputs?


I'm trying to do a quicksort implementation in scheme using a partition that takes two argument, a pivot and a list.

If I were to run:

=> (partition '3 '(5 7 8 6 4 2 1)) 

I want the output to be:

=>;Value: ((2 1) (3 5 7 8 6 4))

I'm using this code:

(define (partition lt? lst)
 (if (null? lst)
     (values '() '())
     (let ((rest (cdr lst)))
       (if (lt? (car lst) (car rest))
           (let ((left (partition lt? rest)))
             (values (cons (car lst) (car left))
                     (cdr left)))
           (let ((right (partition lt? rest)))
             (values (car right)
                     (cons (car lst) (cdr right)))))))

I get the following error:

Output


Solution

  • I wrote this for you

    (define (partition lt? pivot lst)
      ((lambda (s) (s s lst list))
       (lambda (s l* c)
         (if (null? l*)
             (c '() '())
             (let ((x (car l*)))
               (s s (cdr l*)
                  (lambda (a b)
                    (if (lt? x pivot)
                        (c (cons x a) b)
                        (c a (cons x b))))))))))
    

    here is a test

    1 ]=> (partition < '3 '(5 7 8 6 4 2 1))
    ;Value: ((2 1) (5 7 8 6 4))