Arantium Maestum

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

2016-05-08から1日間の記事一覧

Clojureでバブルソート2

そういえばClojureのsequenceはvectorじゃない場合は大抵countがO(n)だった。 bubble-sortでO(n)回bubbleを呼び、bubble内でO(n)回再帰して、その中でO(1)の作業だったはずが、(cond (>= i (count xs)))でもう一回O(n)の作業を入れていたのでO(n3)になる。 …

Clojureでバブルソート

とりあえず書きなぐったもの。 (defn bubble [xs i] (loop [left [] x1 (first xs) [x2 & right :as xs] (rest xs)] (cond (>= i (count xs)) (doall (concat left [x1] xs)) :else (let [[maxx minx] ((juxt max min) x1 x2)] (recur (conj left minx) maxx…

Clojureでインサーションソート

例によってソート実装。これは面白かった。 とりあえず書いてみたのは以下のコード: (defn insert [x sorted] (let [[heads tails] (split-with #(<= % x) sorted)] (concat heads [x] tails))) (defn insertion-sort [xs] (loop [[head & tail :as unsorte…

Clojureでセレクションソート

まあとりあえず。 (defn selection-sort [xs] (loop [unsorted xs, sorted []] (if (empty? unsorted) sorted (let [unsorted-indexed (map vector (range) unsorted) [min-i min-v] (apply min-key second unsorted-indexed) [heads [_ & tails]] (split-at…