2016/05/14

Schemeでクイックソート

先日の納会でソートの話が少し出たのでクイックソートを書いてみました.
書きやすいのでGaucheで.

まず普通に書いてみます.

(define (quick lst)
  (if (null? lst)
      '()
      (let ((first (car lst)))
        (append (quick (filter (lambda (x) (< x first)) lst))
                (filter (lambda (x) (= x first)) lst)
                (quick (filter (lambda (x) (< first x)) lst))))))
gosh> (quick '( 4 7 8 3 9 2 7 3 92 7 1))
(1 2 3 3 4 7 7 7 8 9 92)

普通ですね.
ただfilterで何度もリストの中身を舐めているのが嫌です. ここでstreamを使ってみます.

(use util.stream)
(define (quick lst)
  (stream->list
   (let recur ((s (list->stream lst)))
     (if (stream-null? s)
         stream-null
         (let ((first (stream-car s)))
           (stream-append (recur (stream-filter (lambda (x) (< x first)) s))
                          (stream-filter (lambda (x) (= x first)) s)
                          (recur (stream-filter (lambda (x) (< first x)) s))))))))
gosh> (quick '( 4 7 8 3 9 2 7 3 92 7 1))
(1 2 3 3 4 7 7 7 8 9 92)

リストからストリームへの変換とストリームからリストへの変換が入っているので
効率的になったのかどうか怪しいですが一応期待通りに動いていますね.
どうするのが正解なんでしょう?


© 2022 wat-aro