Clojureでバブルソート２

そういえばClojureのsequenceはvectorじゃない場合は大抵countがO(n)だった。

bubble-sortでO(n)回bubbleを呼び、bubble内でO(n)回再帰して、その中でO(1)の作業だったはずが、(cond (>= i (count xs)))でもう一回O(n)の作業を入れていたのでO(n³)になる。

解決策として、countはbubble内で一回だけ呼んでその後再帰するたびにdecしていく。

(defn bubble [xs i]
  (loop [left                []
         x1                  (first xs)
         [x2 & right :as xs] (rest xs)
         j                   (count xs)]
    (cond (>= i j) 
          (doall (concat left [x1] xs))
          
          :else
          (let [[maxx minx] ((juxt max min) x1 x2)]
            (recur (conj left minx) maxx right (dec j))))))
          
(defn bubble-sort [xs]
  (loop [xs xs, i 0]
    (let [next-xs (bubble xs i)]
      (if (or (>= i (count xs))
              (= xs next-xs))
        xs
        (recur next-xs (inc i))))))

これで計測してみるとO(n²)。

後は読みやすく整理するだけ。だけ、と言いつつそこが一番の考えどころだったりする。