Clojureで基数ソート
Radix Sortとも。
バケツソートのバケツ数を制限して、そのかわり複数回走らせることで
すでにバケツソートを書いたので実装は比較的楽。
(defn radix-sort [xs] (let [bucket-count 100 buckets (into [] (repeat bucket-count [])) max-item (apply max xs) quot-buckets #(quot % bucket-count) rem-buckets #(rem % bucket-count)] (loop [xs xs quots identity] (if (zero? (quots max-item)) xs (let [f (comp rem-buckets quots) add-item (fn [buckets item] (update-in buckets [(f item)] #(conj % item)))] (recur (apply concat (reduce add-item buckets xs)) (comp quots quot-buckets)))))))
O(kn)という、少し複雑な時間コストになる。最大の数字が基数kだったとして、O(n)のバケットソートをk回走らせる理屈になる。