eharetea

Bubble sort a vector in scheme.

Bubble sort a vector in scheme.

Date Created:Sunday October 26th, 2008 06:58 PM
Date Modified:Sunday October 26th, 2008 06:59 PM

;; The order of growth is n^2

(define (bubble-sort! vec)
  (bubbler vec 0)
)

;; BUBBLER WILL LOOP THE LOOP, i.e. EACH TIME BUBBLE WILL INVOKE
;; THE VECTOR-LOOP PROCEDURE ALWAYS STARTING WITH 0, AND THEN
;; TELLING IT TO STOP ONE VALUE FROM THE LAST EACH TIME.
;; i.e. the STOP VALUE is (- (vector-length vec) (+ k 1))
;; AND KEEP IN MIND k increments each time

(define (bubbler vec k)
  (if (= k (- (vector-length vec) 1))
      vec
      (begin
       (vector-loop vec 0 (- (vector-length vec) (+ k 1)))
       (bubbler vec (+ k 1)))))

;; THIS IS THE VECTOR-LOOP, IT WILL COMPARE TWO ELEMENTS AT
;; A TIME FROM n to stop
(define (vector-loop vec n stop)
   (if (= n stop)
       vec
       (let ((val1 (vector-ref vec n)) (val2 (vector-ref vec (+ n 1))))
         (if (> val1 val2)
             (begin
             (vector-set! vec n val2)
             (vector-set! vec (+ n 1) val1)))
         (vector-loop vec (+ n 1) stop))))

(define v1 (vector 5 4 2 8 7 3 1 2 6))

Vector Bubble Sort by Dan Lynch
is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
Based on a work at www.3daet.com
Permissions beyond the scope of this license may be available at http://www.3daet.com