Sort algorithms in Clojure

sorts.clj

(defn insertion-sort [ks]
  (reduce (fn [a x]
            (let [[h t] (split-with #(< % x) a)]
              (concat h [x] t)))
    [] ks))

(defn merge-sort [ks]
  (let [c (count ks)]
    (if (= c 1) ks
      ((fn m [[[ah & ar :as a] [bh & br :as b]]]
         (cond (nil? ah) b
               (nil? bh) a
               (< ah bh) (cons ah (m [ar b]))
               :else     (cons bh (m [a br]))))
       (map merge-sort (split-at (quot c 2) ks))))))

(defn quick-sort [[k & ks]]
  (if (nil? k) []
    (apply #(concat %1 [k] %2)
      (map quick-sort
        (reduce (fn [[a b] x]
                  (if (< k x) [a (conj b x)] [(conj a x) b]))
                [[] []] ks)))))

整列アルゴリズム in Clojure

挿入ソート

(defn insertion-sort [ks]
  (reduce (fn [a x]
            (let [[h t] (split-with #(< % x) a)]
              (concat h [x] t)))
    [] ks))

[] で累積器 a を空ベクタで初期化し,
シーケンス ks の要素を x で順に参照して,
reduce で累算します.
各回で, 累積器 a はそれまでに参照した値が整列された状態で格納されているベクタになるようにします.

(split-with #(< % x) a): 累積器 a の中身を先頭から見て行き, 最初に x 以上の値が見つかった場所未前と, それ以後の二つのシーケンスに分割します.
let [[h t] ...]: 前者を h, 後者を t として,
(concat h [x] t): h, [x] および t を連結して新しい累積器の値とします.
これによって, 整列済みである状態を保持して累積器のシーケンスに要素 x を追加できました.

[x] は要素 x だけからなるベクタです.
(split-with #(< % x) a) は, 1パスで [(take-while #(< % x) a) (drop-while #(< % x) a] と同等の動作を行います.

マージソート

(defn merge-sort [ks]
  (let [c (count ks)]
    (if (= c 1) ks
      ((fn m [[[ah & ar :as a] [bh & br :as b]]]
         (cond (nil? ah) b
               (nil? bh) a
               (< ah bh) (cons ah (m [ar b]))
               :else     (cons bh (m [a br]))))
       (map merge-sort (split-at (quot c 2) ks))))))

let [c (count ks)]: 対象のシーケンスの長さを c とします.
if (= c 1) ks: 長さが 1 ならば整列済みとして与えられたシーケンスそのまま返します.
(split-at (quot c 2) ks): 対象のシーケンスを半分の長さで分割します.
(map merge-sort ...): それぞれをマージソートします.

((fn m [...] ...) ...): 以下の処理を m とし, ソート済みの二つのシーケンスに適用します.
[[ah & ar :as a] [bh & br :as b]]: 二つのソート済みシーケンスをそれぞれ a, b とします. その際, a の先頭の要素を ah, 残りのシーケンスを ar とします. b も同様です.
(nil? ah) b: ah が nil, つまり a が空ならば, b が全体の整列結果です.
(nil? bh) a: bh が nil, つまり b が空ならば, a が全体の整列結果です.
(< ah bh) (cons ah (m [ar b]): ah が bh より小さければ, ar を新しい a, b を新しい b として処理 m を行った結果の先頭に ah を追加したものが全体の整列結果です.
:else (cons bh (m [a br])): ah が bh 以上ならば, a を新しい a, br を新しい b として処理 m を行った結果の先頭に bh を追加したものが全体の整列結果です.

クイックソート

(defn quick-sort [[k & ks]]
  (if (nil? k) []
    (apply #(concat %1 [k] %2)
      (map quick-sort
        (reduce (fn [[a b] x]
                  (if (< k x) [a (conj b x)] [(conj a x) b]))
                [[] []] ks)))))

先頭の要素を k, 残りのシーケンスを ks とします.

ks を, k 以下の要素のシーケンスと, k より大きい要素のシーケンスに分割します.
[(remove #(< k %) ks) (filter #(< k %) ks)] でも構いませんが, 2パスを嫌って,
1パスで

(reduce (fn [[a b] x]
          (if (< k x) [a (conj b x)] [(conj a x) b])
        [[] []] ks)

とします.
map quick-sort で, 両方のシーケンスをクイックソートし,
apply #(concat %1 [k] %2) で, 前者のシーケンス %1, k だけからなるシーケンス [k] および後者のシーケンス %2 を連結します.

実行例

user=> (insertion-sort '(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3))
(1 1 2 3 3 3 4 5 5 5 6 7 8 9 9 9)
user=> (merge-sort '(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3))
(1 1 2 3 3 3 4 5 5 5 6 7 8 9 9 9)
user=> (quick-sort '(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3))
(1 1 2 3 3 3 4 5 5 5 6 7 8 9 9 9)

注意

アルゴリズム実装の演習のためか特殊な条件下以外では, 整列には組込の sort 関数を用いてください.
アルゴリズムに焦点をあてるため, 対象は < で比較可能なオブジェクトのシーケンスとしました.
実利用する場合は, 引数に, オブジェクトを比較するための関数を与えることができるようにして, 且つその比較関数のデフォルトを compare にします.
また, 対象が大きくてもスタックが溢れないためには, 再帰呼出し箇所に lazy-seq を用いた方が良いかもしれません.

Clojure 演習