Emacs Lisp でクイックソート

仕事に疲れたら、人生に疲れたら、素数を数えたり、基礎的なアルゴリズムを復習したり、単純な計算問題を手で解いたりしてみるといい（線形代数の行列演算とか）。

その一環で今日はクイックソートをEmacs Lisp で作成。

(lexical-let*)というマクロで思い通りのクロージャが作れるので、それほど煩雑にはならない。

ついでに、リストだけでなく、Vector 型に対応したものも作ってみた。

また、テストデータの作成ですこしだけ loopマクロを使った。

;; ふつうのクイックソート（リストを昇順ソート）
;; ピボットを左端の要素とする方式
(defun qsort (lat)
  (if (null lat) nil
    (lexical-let* ((piv (car lat))
                   (right (cdr lat))
                   (fn (lambda (a) (< a piv))) )
      (append (qsort (remove-if-not fn right))
              (list piv)
              (qsort (remove-if fn right)) ))))
=> qsort


;; Vectorを昇順ソート（"elt", "vconcat", "subset"などの組み込み関数を利用）
;; ピボットを中央の要素とする方式
(defun vqsort (v)
  (cond
   ((zerop (length v)) nil)
   ((= 1 (length v)) v)
   (t (lexical-let* ((m (/ (length v) 2))
                     (piv (elt v m))
                     (v2 (vconcat (subseq v 0 m) (subseq v (1+ m))))
                     (fn (lambda (a) (< a piv))))
        (vconcat (vqsort (remove-if-not fn v2))
                         (vector piv)
                         (vqsort (remove-if fn v2))) ))))
=> vqsort


;; 実行してみる（リストのソート）
;; (loop ...)は 30 から 1 までの数を要素とするリストを生成
(qsort
 (loop for i from 30 downto 1 append (list i)) )
=> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30)


;; 実行してみる（vectorのソート）
;; (loop ...)は 30 から 1 までの数を要素とするvectorを生成
(vqsort 
 (loop for i from 30 downto 1
       with v
       do (setf v  (vconcat v (vector i)))
       finally (return  v) ))
=> [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30]

結果を見る限り、正しくできたと思われる。

参考

• Sequences Arrays Vectors - GNU Emacs Lisp Reference Manual
• LOOP for Black Belts