[plt-scheme] Do no evil

Owen Astrachan? It takes a 'professor of the teaching profession' to  
tell the world what Knuth said in 1965? I wonder what this tells us  
about wikipedia and CS education.

In case you're wondering: Knuth, vol 3, page 111 original edition.

;; ---

Pictures for teaching a bad algorithm and fancy animations that cost a  
good amount of money to produce make things WORSE not better. Think  
about it. No design recipe needed.



On Mar 8, 2010, at 10:59 AM, wooks . wrote:

> More Wikipedia
>
> Due to its simplicity, bubble sort is often used to introduce the  
> concept of an algorithm, or a sorting algorithm, to introductory  
> computer science students. However, some researchers such as Owen  
> Astrachan have gone to great lengths to disparage bubble sort and  
> its continued popularity in computer science education, recommending  
> that it no longer even be taught.[1]
> The Jargon file, which famously calls bogosort "the archetypical  
> perversely awful algorithm", also calls bubble sort "the generic bad  
> algorithm".[2] Donald Knuth, in his famous book The Art of Computer  
> Programming, concluded that "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", some of which he then  
> discusses.
>
> ...and in case my previous post failed  (not used to posting from  
> email)
>
> However, one significant advantage that bubble sort has over most  
> other implementations, even QuickSort, is that the ability to detect  
> that the list is sorted is efficiently built into the algorithm.  
> Performance of bubble sort over an already-sorted list (best-case)  
> is O(n). By contrast, most other algorithms, even those with better  
> average-case complexity, perform their entire sorting process on the  
> set and thus are more complex. However, Insertion sort also has this  
> mechanism, and also performs better on a list that is substantially  
> sorted (having a small number ofinversions).
>
>
>
> > Date: Mon, 8 Mar 2010 09:53:44 -0600
> > Subject: Re: [plt-scheme] Do no evil
> > From: robby at eecs.northwestern.edu
> > To: matthias at ccs.neu.edu
> > CC: wookiz at hotmail.com; plt-scheme at list.cs.brown.edu
> >
> > I tried to find that quote, but didn't find anything better than  
> what
> > it says in the "in practice" section of Wikipedia.
> >
> > (And, of course, we are in a loop here, but this is a new piece of
> > information related to the loop-- I don't mean for us to cover any  
> old
> > ground again. Apologies in advance if we head off thataway.)
> >
> > Robby
> >
> > On Mon, Mar 8, 2010 at 9:47 AM, Matthias Felleisen <matthias at ccs.neu.edu 
> > wrote:
> > >
> > > 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
> > >>>
> > >
> > >
>
> Got a cool Hotmail story? Tell us  
> now_________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme