CODEWITHSUNDEEP
schemequicksort
Sarah
Sarah

Reputation: 2903

Writing partition for quicksort in scheme

I am having a lot of trouble with writing scheme...

I am trying to write quicksort using scheme. I have seen tons of answers but they don't really make any sense to me and this is mostly because I barely understand functional programming at all.

I have defined my pivot like this:

(define (pivot lis)
  (car lis))

That works fine (and is easy to write..)

For my understanding of the partition function, you have the original list and then you split it into 2 new lists, one that contains values larger than the pivot, and one that contains values smaller or equal to the pivot.

This is how I've tried to implement it:

(define (partition lis)
  (if (null? lis) '())
  (else (lambda (lis1 lis2)
          (if (< (car lis) pivot) append lis1)
          (partition (append lis2)))))

This is the error I'm getting: . else: not allowed as an expression in: (else (lambda (lis1 lis2) (if (< (car lis) pivot) append lis1) (partition (append lis2))))

I am not really sure how to do this, any ideas on how I can make this work? Or is my reasoning off?

Upvotes: 1

Views: 704

Answers (1)

Rptx
Rptx

Reputation: 1189

(define (partition ls)
  (partition-aux ls (pivot ls) '() '()))

(define (parition-aux ls pivot smaller larger)
  (cond
    ((empty? ls) (list smaller larger))
    ((< (car ls) pivot)
     (parition-aux (cdr ls) pivot (cons (car ls) smaller) larger))
    (else
     (partition-aux (cdr ls) pivot smaller (cons (car ls) larger)))))

you need to define another function to do the job. because you need 2 more arguments to hold the list of smaller and larger numbers. This is one way of doing it. there are other ways that are shorter to type. but I wanted to be explicit.

Upvotes: 1

Related Questions