[plt-scheme] Do no evil

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
http://clk.atdmt.com/UKM/go/195013117/direct/01/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20100308/030fffb9/attachment.html>