Home > Project > Quicksort in Scheme

Quicksort in Scheme

A little while back, I challenged myself to write a Scheme implementation of quicksort. After all, it’s a recursive algorithm, and Scheme is nothing if not recursive, and it seemed like a fun change of pace from writing algorithms in a procedural language.

; Quicksort a proper list
(define (quicksort lst)
  (cond
    ((null? lst)
     '())
    (else (append (quicksort (find-smaller-or-equal
                              (cdr lst) (car lst)))
                  (cons (car lst)
                        (quicksort (find-larger
                                    (cdr lst) (car lst))))))))

(define (find-larger lst lower-bound)
  (cond
    ((null? lst)
     '())
    ((<= (car lst) lower-bound)
     (find-larger (cdr lst) lower-bound))
    (else
     (cons (car lst)
           (find-larger (cdr lst) lower-bound)))))

(define (find-smaller-or-equal lst upper-bound)
  (cond
    ((null? lst)
     '())
    ((> (car lst) upper-bound)
     (find-smaller-or-equal (cdr lst) upper-bound))
    (else (cons (car lst)
                (find-smaller-or-equal (cdr lst) upper-bound)))))

I had a good time writing this, and it’s one of the shortest quicksorts I’ve seen, though I make no claims as to its efficiency.

Advertisements
Categories: Project
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: