; Precondition: smaller? is a procedure that can be
; applied to any two elements of lst. It should return
; #t iff the first argument is ``smaller'' than the second.
(define bubblesort
    (lambda (lst smaller?)
        (helper lst smaller? (- (length lst) 1))
    )
)

; Bubblesorts the first n elements of lst. Returns a
; new list with the first n elements of lst sorted,
; followed by the rest of lst unchanged.
; Precondition: n < (length list).
(define helper
    (lambda (lst smaller? n)
        (if (<= n 0)
            lst
            (helper (bubbleFirstN lst smaller? n)
                    smaller?
                    (- n 1)
            )
        )
    )
)

; Does a single "bubble run".
; Precondition: n < (length lst)
(define bubbleFirstN
    (lambda (lst smaller? n)
        (cond ( (= n 0) lst )
              ( (smaller? (car lst) (cadr lst))
                    (cons (car lst)
                          (bubbleFirstN (cdr lst)
                                        smaller?
                                        (- n 1))
                    )
              )
              ( else (cons (cadr lst)
                           (bubbleFirstN (cons (car lst)
                                               (cddr lst))
                                         smaller?
                                         (- n 1))
                     )
              )
        )
    )
)