Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uunet!wuarchive!psuvax1!psuvm!cunyvm!byuvm!byuvax!taylorj
From: taylorj@yvax.byu.edu
Newsgroups: comp.edu
Subject: Re: Bubble Sort (was ALGORITHMS ANYBODY?)
Message-ID: <1503taylorj@yvax.byu.edu>
Date: 25 Aug 90 20:57:18 GMT
Lines: 38

In <12868@june.cs.washington.edu>, pattis@cs.washington.edu (Richard Pattis)
writes:

>What exactly is wrong with bubble sort? It is the smallest sorting algorithm
>to state (in most imperative programming languages), and is the easiest one
>to prove correct (assuming a Swap procedure). For small array sizes, its
>performance is just fine.  If a student ever has to reconstruct a sorting
>method from scratch, he/she will have the highest probability of getting
>bubble sort right (higher than any other algorithm I can think of).  There
>are even sets of data (almost sorted) where bubble sort can do better than
>many "asymptotically faster" sorting algorithms.

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.

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.


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