クイックソート(『はじめてのLisp関数型プログラミング』(p.120))

qsort.rkt

#lang racket

(require rackunit)

(define (qsort l)
  (if (null? l)
      l
      (qsort2 (car l) (cdr l) '() '())))

(define (qsort2 p l left right)
  (if (null? l)
      (append (qsort left) (cons p (qsort right)))
      (let ([append-elem (car l)]
            [next-l (cdr l)])
        (if (< append-elem p)
            (qsort2 p next-l (cons append-elem left) right)
            (qsort2 p next-l left (cons append-elem right))))))

(define (iqsort l)
  (if (or (null? l) (empty? l))
      l
      (let ([p (car l)]
            [left '()]
            [right '()])
        (for ([e (cdr l)])
          (if (< e p)
              (set! left (cons e left))
              (set! right (cons e right))))
        (append (iqsort left) (list p) (iqsort right)))))

(check-equal? (qsort '(2 1 3 5 4)) '(1 2 3 4 5))
(check-equal? (iqsort '(2 1 3 5 4)) '(1 2 3 4 5))