Arantium Maestum

プログラミング、囲碁、読書の話題

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回走らせる理屈になる。