Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!usc!snorkelwacker!mit-eddie!uw-beaver!ubc-cs!manis From: manis@cs.ubc.ca (Vincent Manis) Newsgroups: comp.edu Subject: Re: Bubble Sort (was ALGORITHMS ANYBODY?) Message-ID: <9341@ubc-cs.UUCP> Date: 29 Aug 90 19:48:18 GMT References: <1503taylorj@yvax.byu.edu> <29486:Aug2903:26:2990@kramden.acf.nyu.edu> Sender: news@cs.ubc.ca Distribution: usa Organization: Institute for Pure and Applied Eschatology Lines: 23 One of my formerly-treasured possessions (since lost in one or another move) was an HP 21MX microprogramming manual (the 21MX was the precessor of the still-marketed HP1000 minicomputer series). This marvellous document showed how you could speed up a Fortran subroutine by microprogramming it. Which subroutine? You guessed it: bubble sort. Actually, bubble sort is very useful in a data structures course. I like to demonstrate plain bubble sort, bubble sort with flag, and shaker sort (aka ``Double Bubble''). Then, using Wirth's results from ``Algorithms+Data Structures=Programs'', I show how each ``optimization'' makes it worse on the average case. As well as two-tape sorts, don't forget that Shell sort (which is something of a curiosity now, albeit with mathematical interest) is based on bubble sort. Truly, there is nothing useless...except perhaps MVS. -- \ Vincent Manis "There is no law that vulgarity and \ Department of Computer Science literary excellence cannot coexist." /\ University of British Columbia -- A. Trevor Hodge / \ Vancouver, BC, Canada V6T 1W5 (604) 228-2394