From f69448ded971deb6a702894499c718e4a26857dd Mon Sep 17 00:00:00 2001 From: bd Date: Sat, 18 May 2024 23:08:30 -0600 Subject: Finish bubble-sort --- bubble/bubble-sort.scm | 33 ++++++++++++++++++++++++++++++++- 1 file changed, 32 insertions(+), 1 deletion(-) (limited to 'bubble/bubble-sort.scm') 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))) -- cgit v1.2.3