2 files changed, 56 insertions, 1 deletions
diff --git a/bubble/bubble-sort-test.scm b/bubble/bubble-sort-test.scm
index c870577..daa59d7 100644
--- a/bubble/bubble-sort-test.scm
+++ b/bubble/bubble-sort-test.scm
@@ -8,5 +8,29 @@
   '()
   (bubble-sort '()))
 
+(test-equal "in-order"
+  '(0 1)
+  (bubble-sort '(0 1)))
+
+(test-equal "in-order-large"
+  '(0 1 2 5 6 9 19 101)
+  (bubble-sort '(0 1 2 5 6 9 19 101)))
+
+(test-equal "single-swap"
+  '(0 1)
+  (bubble-sort '(1 0)))
+
+(test-equal "double-swap"
+  '(0 1 5 6)
+  (bubble-sort '(1 0 6 5)))
+
+(test-equal "total-reversal"
+  '(0 1 2 3 4 5 6 7 8 9)
+  (bubble-sort '(9 8 7 6 5 4 3 2 1 0)))
+
+(test-equal "random-scramble"
+  '(-9 -2 0 11 45)
+  (bubble-sort '(-2 45 0 11 -9)))
+
 
 (test-end "harness")
diff --git a/bubble/bubble-sort.scm b/bubble/bubble-sort.scm
index 6efa819..fccaa4d 100644
--- a/bubble/bubble-sort.scm
+++ b/bubble/bubble-sort.scm
@@ -1,4 +1,35 @@
 (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)))