Bubble sort implementation in Clojure.

bubblesort.clj

(defn bubble-step [coll was-changed less?]
  (if (second coll)
    (let [[x1 x2 & xs] coll
          is-less-than (less? x1 x2)
          smaller (if is-less-than x1 x2)
          larger (if is-less-than x2 x1)
          is-changed (or was-changed (not is-less-than))
          [sorted is-sorted] (bubble-step (cons larger xs) is-changed less?)]
      [(cons smaller sorted) is-sorted])
    [coll (not was-changed)]))

(defn bubble-sort [coll less?]
  (loop [[coll is-sorted] [coll false]]
    (if is-sorted
      coll
      (recur (bubble-step coll is-sorted less?)))))

(bubble-step [40 32 1 300] false <)
(bubble-step [1 2 3] false <)

(bubble-sort [40 32 1 300] <)

(bubble-sort [1 2 3 4 5 6] <)


(comment
  
  ;step1
  [40 32 1 300]
  
  smaller 32
  larger 40
  xs [1 300]
  was-changed true
  
    ;step2
    [40 1 300]
  
    smaller 1
    larger 40
    xs [300]
    was-changed true
  
      ;step3
      [40 300]
      smaller 40
      larger 300
      xs []
      was-changed false
  
      [40 300] false
    
    [1 40 300] true
    
  [32 1 40 300] true
  
 )


(comment
  
  ;step1
  [1 2 3 4]
  
  smaller 1
  larger 2
  xs [3 4]
  was-changed false
  
    ;step2
    [2 3 4]
  
    smaller 2
    larger 3
    xs [4]
    was-changed false
  
      ;step3
      [3 4]
      smaller 3
      larger 4
      xs []
      was-changed false
  
      [3 4] false
    
    [2 3 4] false
    
  [1 2 3 4] false
  
 )