blob: fccaa4df318b782c81dbd4d34b732f5398b76c52 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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)))
|
