;; Time Complexity O(n^2)
;; Space Complexity O(n) — a persistent vector is rebuilt, never mutated

;; one walk through: every neighbouring pair out of order is swapped
(defn one-pass [v]
  (reduce (fn [acc i]
            (let [a (acc i), b (acc (inc i))]
              (if (> a b) (assoc acc i b (inc i) a) acc)))
          v
          (range (dec (count v)))))

;; passes repeat until a pass changes nothing
(defn bubble-sort [coll]
  (loop [v (vec coll)]
    (let [w (one-pass v)]
      (if (= w v) v (recur w)))))

(def items [4 1 5 3 2])
(def sort-items (bubble-sort items))
;; sort-items is [1 2 3 4 5]

(prn items)
(prn sort-items)
(println "same as built-in sort:" (= sort-items (sort items)))