diff options
| -rw-r--r-- | bubble/bubble-sort-test.scm | 24 | ||||
| -rw-r--r-- | bubble/bubble-sort.scm | 33 | ||||
| -rw-r--r-- | fibonacci/fibonacci.scm | 2 | ||||
| -rwxr-xr-x | prime/prime.scm | 2 |
4 files changed, 58 insertions, 3 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))) diff --git a/fibonacci/fibonacci.scm b/fibonacci/fibonacci.scm index 8563587..1858624 100644 --- a/fibonacci/fibonacci.scm +++ b/fibonacci/fibonacci.scm @@ -11,7 +11,7 @@ as a list" fibonacci sequence." (if (zero? k) lst - (fibonacci-helper (- k 1) + (fibonacci-helper (1- k) n2 (+ n1 n2) (append lst (list n1))))) diff --git a/prime/prime.scm b/prime/prime.scm index e12dfb4..89915a1 100755 --- a/prime/prime.scm +++ b/prime/prime.scm @@ -14,4 +14,4 @@ by attempting division by number D,D-1,D-2..." #t (if (equal? (remainder n d) 0) #f - (prime-helper n (- d 1))))) + (prime-helper n (1- d))))) |