破壊的なクイックソートを実装してみた

C言語だとかの言語では普通に採用されている破壊的なクイックソートを Scheme で実装してみた。C言語でもクイックソートは実装したことなんかないけど。

C言語でいえば添え字でなくポインターを直接扱うような実装ということ。C言語のと違うのは Scheme のポインターは整数でないからポインターの大小比較（low < high）ができないこと。というかC言語でも配列でなく線形リストでやるなら同じことだけど。

(define (quicksort! objects <<)
  (or
    (null? objects)
    (null? (cdr objects))
    (letrec
      ((quicksort!-core
        (lambda (cell-first cell-last)
          (unless (eq? cell-first cell-last)
            (call-with-values
              (lambda ()
                (let*
                  (
                  (lessers-cell cell-first)
                  (lessers-cell-pre #f)
                  (pivot-cell cell-last)
                  (pivot-cell-object (car pivot-cell))
                  )
                  (do ((do-cell cell-first (cdr do-cell)))
                    ((eq? do-cell pivot-cell))
                    (when (<< (car do-cell) pivot-cell-object)
                      (let ((l (car lessers-cell)))
                        (set-car! lessers-cell (car do-cell))
                        (set-car! do-cell l))
                      (set! lessers-cell-pre lessers-cell)
                      (set! lessers-cell (cdr lessers-cell))))

                  (let ((l (car lessers-cell)))
                    (set-car! lessers-cell pivot-cell-object)
                    (set-car! pivot-cell l))

                  (values
                    lessers-cell-pre
                    (and (not (eq? lessers-cell pivot-cell))
                      (cdr lessers-cell)))))

              (lambda (pre post)
                (when (pair? pre)
                  (quicksort!-core cell-first pre))
                (when (pair? post)
                  (quicksort!-core post cell-last))))))
      )) ; quicksort!-core
      (quicksort!-core objects
        (let last-pair ((os objects))
          (if (null? (cdr os))
            os
            (last-pair (cdr os)))))))
  objects)

おためし。

(display
  (quicksort!
    (list #\H #\e #\l #\l #\o #\, #\W #\o #\r #\l #\d #\.)
    char<?))
(newline)

(, . H W d e l l l o o r)

破壊的なクイックソートができてしまえば非破壊版は簡単。

(define (quicksort objects <<)
  (quicksort! (map values objects) <<))

Copilot 版

自分で上のコードを考えたあと、 Copilot に指示をだして、C言語の線形リストで同じコードを書かせてみたら。自分が作ったコードよりもシンプルで分かりやすのが出てきた。

そのC言語のコードを Scheme に焼き直して、なおかつスワップ部分を関数からマクロに変更したりだとかのちょっと手を加えたけど、基本はそのままの逐語訳的なコード。

(define (quicksort! objects less?)
  (or (null? objects) (null? (cdr objects))
    (let-syntax
      ((swap-object! ;; 効率のため関数でなくマクロで実装
        (syntax-rules ()
          ((swap-object! a b)
            (unless (eq? a b)
              (let ((car_a (car a)))
                (set-car! a (car b))
                (set-car! b car_a)))))))
      (letrec
        ((quicksort-core (lambda (start end)
          (or (null? start) (eq? start end) (eq? (cdr start) end)
            (let
              ((pivot
                (let
                  (
                  (pivot-object (car start))
                  (lessers-last start)
                  )
                  (do ((cell (cdr start) (cdr cell))) ((eq? cell end))
                    (when (less? (car cell) pivot-object)
                      (set! lessers-last (cdr lessers-last))
                      (swap-object! lessers-last cell)))
                  (swap-object! lessers-last start)
                  lessers-last)))
              (quicksort-core start pivot)
              (quicksort-core (cdr pivot) end))))
        ))
        (quicksort-core objects (list)))))
  objects)

おためし

(display (quicksort! (list #\H #\e #\l #\l #\o #\, #\W #\o #\r #\l #\d #\.) char<?))
(newline)

(, . H W d e l l l o o r)

感想

こんなにシンプルにクイックソートが書けるなら、空で暗唱できるぐらいに身に着けておいても損はなさそう。

それにしても、業務のちょっとしたその場限りの作業の自動化のコードを Copilot に書かせたことがあったけど、その時も感じたけど、ちょっとしたコードなら Copilot に書かせると速いし楽ができる。Scheme のコードを以前に書かせたときは、ロジックに間違いがあったり、カッコの対応が抜けていたり、存在しない関数を呼び出していたり、「;; 細かい実装...」みたいに肝心のところが書かれてなかったりとか、けっこう抜けもあったけど。実は上のコードにも抜けがあるかも？そう考えると安直には使うべきではなさそう？

こんかいC言語のコードを久しぶりに書いてみておもったのは、C言語にも Scheme の強力なマクロの仕組みがあればいいのにということ。C言語のコードをS式で表現するという、河合史郎さんの CiSE というやつを思い出した。