<html> <head> <style></style> </head> <body class='hmmessage'> <div> </div>"the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems", Thinking about it, isn't that enough to recommend it. <div> </div><div>What would Knuth say about using pictures and animations to teach programming. > CC: wookiz@hotmail.com; plt-scheme@list.cs.brown.edu > From: matthias@ccs.neu.edu > To: robby@eecs.northwestern.edu > Subject: Re: [plt-scheme] Do no evil > Date: Mon, 8 Mar 2010 10:47:16 -0500 > > > 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@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@i (vector-ref v i))) > >> (begin > >> (vector-set! v i (vector-ref v (+ i 1))) > >> (vector-set! v (+ i 1) v@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 > >> > </div> <hr />Do you have a story that started on Hotmail? <a href='http://clk.atdmt.com/UKM/go/195013117/direct/01/' target='_new'>Tell us now</a></body> </html>