読者です 読者をやめる 読者になる 読者になる

Arantium Maestum

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

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)。