[plt-scheme] Do no evil
Knuth wrote this up in the 1960s. Anyone who teaches bubble sort
in the 20xy is teaching 1970s computer science. But I think I am
now in some kind of loop with wooks.
On Mar 8, 2010, at 10:44 AM, Robby Findler wrote:
> Continuing my contrarianocity: When I was taught the bubble sort, I
> wish that my teacher had taken the time to explain bubble sort's place
> in the pantheon of sorting algorithms (there is essentially no metric
> under which it better than some other sort, with the possible
> exception of ease of implementation in Fortran 70).
>
> Robby
>
> On Mon, Mar 8, 2010 at 9:39 AM, Matthias Felleisen <matthias at ccs.neu.edu
> > wrote:
>>
>> I have taken Veer's understanding to derive a relatively short
>> form of bubble sort in the plain Scheme language:
>>
>> (define (bsort v)
>> (define (sweep v i clean?)
>> (cond
>> [(= i (- n 1)) (if clean? v (sweep v 0 true))]
>> [else (if (<= (vector-ref v i) (vector-ref v (+ i 1)))
>> (sweep v (+ i 1) clean?)
>> (sweep (swap v i) (+ i 1) false))]))
>> (define n (vector-length v))
>> ;; IN
>> (sweep v 0 true))
>>
>> ;; swap: factored out as suggested by Noel,
>> ;; do it with build-vector and weep! bubble
>> ;; demos how bad FP's performance can be :-)
>>
>> But I have done so in ASL just to demonstrate that it is feasible.
>>
>> You start with the generative recursion idea of bubbling through
>> the array until there are no more out of place items left. Then
>> you're done. Then you 'edit' the program with two observation.
>> If you were in #lang scheme, you'd come up with the above
>>
>> The derivation is appended below. -- Matthias
>>
>>
>>
>> ;; [Vec Number] -> [Vec Number]
>> ;; create a sorted version of v
>> ;; effect: modify v
>> (define (bsort.v0 v)
>> (local (;; Result = (list [Vec Number] Boolean)
>>
>> ;; [Vec Number] -> [Vec Number]
>> ;; (effect) create a sorted version of v
>> ;; generative recursion: swap-all until nothing to swap
>> anymore
>> ;; termination: there are only a finite number of swaps
>> (define (generative-driver v)
>> (local ((define v+flag (sweep v))
>> (define newv (first v+flag))
>> (define clean? (second v+flag)))
>> (if clean? v (generative-driver v))))
>>
>> ;; [Vec Number] -> Result
>> ;; (effect) swap all out of place neighbors throughout
>> vector
>> (define (sweep v)
>> (local (;; [Vec Number] N Boolean -> Result
>> ;; accumulators: [0,i) is bubbled -- clean? no
>> swaps so
>> far
>> (define (sweep v i clean?)
>> (cond
>> [(= i (- (vector-length v) 1)) (list v
>> clean?)]
>> [else (if (<= (vector-ref v i) (vector-ref v
>> (+ i
>> 1)))
>> (sweep v (+ i 1) clean?)
>> (sweep (swap v i) (+ i 1)
>> false))])))
>> (sweep v 0 true))))
>> ;; IN
>> (generative-driver v)))
>>
>> ;; fold the geneative-driver into the sweep function
>> ;; observation: the base case packages up the result,
>> ;; which is immediately unfolded and used for another call
>>
>> (define (bsort.v1 v)
>> (local (;; [Vec Number] -> [Vec Number]
>> ;; (effect) swap all out of place neighbors throughout
>> vector
>> (define (sweep v)
>> (local (;; [Vec Number] N Boolean -> Result
>> ;; accumulators: [0,i) is bubbled -- clean? no
>> swaps so
>> far
>> (define (sweep v i clean?)
>> (cond
>> [(= i (- (vector-length v) 1))
>> (if clean? v (sweep v 0 true))]
>> [else (if (<= (vector-ref v i) (vector-ref v
>> (+ i
>> 1)))
>> (sweep v (+ i 1) clean?)
>> (sweep (swap v i) (+ i 1)
>> false))])))
>> (sweep v 0 true))))
>> ;; IN
>> (sweep v)))
>>
>> ;; eliminate the indirection from 1-ary sweep through 1-ary sweep
>> ;; lift the vector-length computation
>>
>> (define (bsort v)
>> (local (;; [Vec Number] N Boolean -> Result
>> ;; accumulators: [0,i) is bubbled -- clean? no swaps so far
>> (define (sweep v i clean?)
>> (cond
>> [(= i (- n 1)) (if clean? v (sweep v 0 true))]
>> [else (if (<= (vector-ref v i) (vector-ref v (+ i 1)))
>> (sweep v (+ i 1) clean?)
>> (sweep (swap v i) (+ i 1) false))]))
>> ;; where
>> (define n (vector-length v)))
>> ;; IN
>> (sweep v 0 true)))
>>
>> ;;
>> -----------------------------------------------------------------------------
>> ;; auxiliaries
>>
>> ;; [Vec Number] N -> [Vec Number]
>> ;; swap items i and i+1 in v
>> (define (swap v i)
>> (local ((define v at i (vector-ref v i)))
>> (begin
>> (vector-set! v i (vector-ref v (+ i 1)))
>> (vector-set! v (+ i 1) v at i)
>> v)))
>>
>> ;;
>> -----------------------------------------------------------------------------
>> ;; tests
>>
>> (define (generate-test) (vector 3 1 9 8 5 6 7 0 4 2))
>> (define swapped0 (vector 1 3 9 8 5 6 7 0 4 2))
>> (define swapped2 (vector 3 1 8 9 5 6 7 0 4 2))
>> (define sorted (vector 0 1 2 3 4 5 6 7 8 9))
>>
>> (check-expect (swap (generate-test) 0) swapped0)
>> (check-expect (swap (generate-test) 2) swapped2)
>>
>> (check-expect (bsort (generate-test)) sorted)
>>
>> _________________________________________________
>> For list-related administrative tasks:
>> http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>>