(define-module (bubble-sort))

(define-public (bubble-sort lst)
  (vector->list (bubble-sort-helper (list->vector lst))))

(define (bubble-sort-helper vect)
  "Recursively performs a bubble sort on VECT,
stopping only when no elements were swapped."
  (let ((vect-old (vector-copy vect)))
    (try-swap-all vect)
    (if (equal? vect-old vect)
        vect
        (bubble-sort-helper vect))))

(define (try-swap-all vect)
  "Performs a single iteration of the bubble sort
algorithm on VECT."
  (do ((i 0 (1+ i)))
      ((> i (- (vector-length vect) 2)))
    (try-swap vect i (1+ i))))

(define (try-swap vect i j)
  "Given two indices in ascending order, swap the
indices in VECT if the element at i is greater than
the element at j."
  (cond
   ((> i j) (error "Bad arguments passed to try-swap: i > j"))
   ((> (vector-ref vect i) (vector-ref vect j)) (swap! vect i j))
   (else vect)))

(define (swap! vect i j)
  "Swap the ith and jth elements in VECT."
  (let ((tmp (vector-ref vect i)))
    (vector-set! vect i (vector-ref vect j))
    (vector-set! vect j tmp)))