[plt-scheme] Do no evil

My version using simple recursion (not an improvement):

(define (bubble-sort array)
  (let ([swapped? (swap-all array)])
    (cond
      [swapped? (bubble-sort array)]
      [else array])))


(define (swap-all array)

  (define array-length (vector-length array))

  (define (compare-and-swap i swapped?)
    (cond
      [(= i (- array-length 1)) swapped?]
      [else (let ([i-th (vector-ref array i)]
                  [i+1 (vector-ref array (+ i 1))])
              (cond
                [(<= i-th i+1) (compare-and-swap (+ i 1) swapped?)]
                [else (begin
                        (vector-set! array i i+1)
                        (vector-set! array (+ i 1) i-th)
                        (compare-and-swap (+ i 1) #t))]))]))
  (compare-and-swap 0 #f))




On Mon, Mar 8, 2010 at 12:45 PM, wooks . <wookiz at hotmail.com> wrote:
>
> I have to show my class an array bubblesort. I refused to show them do - let
> the imperative guy introduce them to that evil stuff - methinks. So heres my
> effort which my guts tell me is not the best and I'm sure at some point the
> design recipe went out the window (first time I've fallen off the wagon).
> (define (bubble-sort array)
>   (local [(define any-changes? true)
>           (define (sink-the-largest starting-idx ending-idx)
>             (if (= starting-idx ending-idx)
>                 (bubble-sort ending-idx)
>                 (begin
>                   (local [(define current-value (vector-ref array
> starting-idx))
>                           (define next-value (vector-ref array (add1
> starting-idx)))]
>                     (when (> current-value next-value)
>                       (begin
>                         (vector-set! array starting-idx next-value)
>                         (vector-set! array (add1 starting-idx)
> current-value)
>                         (set! any-changes? true))))
>                   (sink-the-largest (add1 starting-idx) ending-idx))))
>
>           (define (bubble-sort ending-idx)
>             (if any-changes?
>                 (begin
>                   (set! any-changes? false)
>                   (sink-the-largest 0 (sub1 ending-idx)))
>
>                 array))]
>     (bubble-sort (vector-length array))))
> (bubble-sort (vector 92 4 2 32 92 18 16 34 16 32 10))
> Then I start thinking. The students will almost inevitably have to write
> some imperative code but some of them have figured out and bought into my
> strategy - use Scheme wherever you can - because it's "easier" to write.
> Taking that one step further I thought heck - if teach them do they might be
> able to do all their coding in Scheme (if they want to).
> Given that I had just convinced them (I think) why assignment should only be
> used where necessary my misgivings were mitigated by this passage from
> Dyvbig's book
> "Although looping constructs in most languages require that the loop
> iterands be updated via assignment, do requires the loop iterands val ... to
> be updated via rebinding. In fact, no side effects are involved in the
> evaluation of a do expression unless they are performed explicitly by its
> subexpressions."
> My effort with do is also nicer shorter and clearer
> (define (bubble-sort array)
>   (local ([define end (sub1 (vector-length array))]
>           [define any-changes? false])
>     (do [(i 0 (add1 i))]
>       ((= i end) (if any-changes? (bubble-sort array) array))
>       (local ([define current (vector-ref array i)]
>               [define next (vector-ref array (add1 i))])
>         (when (> current next)
>           (set! any-changes? true)
>           (vector-set! array (add1 i) (max current next))
>           (vector-set! array i (min current next)))))))
> I'd welcome improvements on my doless effort (no HOF's - it's beyond the
> scope of what I am teaching) that I could also show them.
>
>
>
>
> ________________________________
> Do you want a Hotmail account? Sign-up now - Free
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
>