Skip to content

Instantly share code, notes, and snippets.

@kohyama
Last active August 29, 2015 13:58
Show Gist options
  • Save kohyama/10232624 to your computer and use it in GitHub Desktop.
Save kohyama/10232624 to your computer and use it in GitHub Desktop.
Sort algorithms in Clojure
(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)))))
@kohyama
Copy link
Author

kohyama commented Apr 9, 2014

整列アルゴリズム 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]): ahbh より小さければ, ar を新しい a, b を新しい b として処理 m を行った結果の先頭に ah を追加したものが全体の整列結果です.
:else (cons bh (m [a br])): ahbh 以上ならば, 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 演習

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment