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 min-i unsorted) new-unsorted (concat heads tails) new-sorted (conj sorted min-v)] (recur new-unsorted new-sorted)))))
min-v
の値が二箇所から帰ってくるのが嫌な感じ(一つは_で無視している)。効率のいいmin-index
的な関数があれば解決するのだが・・・
あと調べていて見つけたmap-index
の存在意義がよくわからない。(map f (range) col)
の方が何が起きてるかはっきりしていていいと思う。transducerとして使えるのがメリットなんだろうか。
アルゴリズム的にはn回ループして最小値をその都度摘出していく。当然ながら効率は悪い。時間的にO(n2)。