Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!wuarchive!mit-eddie!uw-beaver!uw-june!pattis
From: pattis@cs.washington.edu (Richard Pattis)
Newsgroups: comp.edu
Subject: Re: Bubble Sort (was ALGORITHMS ANYBODY?)
Summary: I'll stop after this posting
Message-ID: <12892@june.cs.washington.edu>
Date: 26 Aug 90 18:07:04 GMT
References: <1503taylorj@yvax.byu.edu>
Organization: U of Washington, Computer Science, Seattle
Lines: 54

In article <1503taylorj@yvax.byu.edu>, taylorj@yvax.byu.edu writes:
> In <12868@june.cs.washington.edu>, pattis@cs.washington.edu (Richard Pattis)
> writes:
> 
> 
> I have never understood why people think the bubble sort is most intuitive.
> Think about how you sort when you do it by hand.  Many people use a "pile
> sort", by dividing the domain into sections and putting each item into the
> pile for its corresponding section, then sorting all the piles together.
> The closest analogue to this would be a merge sort.  Many people pull out
> the highest or lowest items and put them at the end or beginning. The
> closest computer analogue here is a double-ended selection sort.
> 
> Nobody I know of makes multiple passes through a bunch of objects and swaps
> items that are out of order, as in a bubble sort.  This is simply not
> intuitive (although it is an easy process to understand and assimilate).
> 
> IMHO, the very simplest sort to understand and recreate is a selection sort.
> You simply find the largest item and put it at one end.  The difference in
> the amount of code required for the selection sort and the bubble sort is
> miniscule, yet the performance difference is substantial.
> 

In bubble sort, the absolute slowest one, all you need are two loops, both
having the same bounds; you need no extra variables.  The lines of code may
be about the same, but I'll argue there are many fewer dependent details to
remember. I never stated that bubble sort is "most intuitive", only that
after they learn it, more students can reproduce it correctly than any other
sorting methods.


> I have been dumbstruck (and deeply saddened) to see supposedly professional
> programs which use a bubble sort.  Those who teach bubble sorts as anything
> more than an intellectual curiosity should be subjected to Chinese water
> torture.

  These are absolutely two different concerns. If introductory instructors
are to be blamed for the sorting methods used by "professionals" then we are
all (instructors and users) in alot of trouble.

  Please note that in my previous posting I went to some lengths to explain
what my students learn subsequently in my classes.


> Jim Taylor
> Microcomputer Support for Curriculum   |
> Brigham Young University               |   Bitnet: taylorj@byuvax.bitnet
> 101 HRCB, Provo, UT  84602             |   Internet: taylorj@yvax.byu.edu


Rich Pattis

I'll continue this discussion off-net with anyone, but I feel at this point
I'm polluting usenet (some would argue my first message was).