[net.sources] A Simple Bubble Sort Function, glass houses

bradley@godot.UUCP (Bradley C. Kuszmaul) (06/11/84)

Not nice to call someone an idiot, especially when you show your own ... er
... failure to keep up with the field.

The selection sort that you described is really no better than the bubble
sort under most conditions:
  bubble sort:  best time:  n steps
                worst time: n^2 steps
  selection sort: best time = worst time = 0.5*(n^2) steps
The selection sort is only better by a factor of two under the conditions
most favorable to it, and is sometimes worse by a factor of 0.5*n.  The
conditions under which bubble sort will win are when a file is "partly
sorted" already (i.e. the farthest a given element will have to travel
is small)

For good sorting algorithms, try quicksort (n^2 at worst n*log n at best,
with the "best" conditions much less restrictive than for bubble sort),
or something else.  (Quicksort and other sorting algorithms are discussed
in "Software Tools" by Kernighan and Plaugher (Excuse the spelling and possibly
incorrect name of the book) and "The Art of Computer Programming, vol II 
Sorting and Searching" by Knuth.

 --Bradley C. Kuszmaul
  {decvax!cca,ihnp4!mit-eddie,allegra!ias}!godot!bradley,
  "godot!bradley@mit-eddie"@MIT-XX.ARPA
-- 
  {decvax!cca,ihnp4!mit-eddie,allegra!ias}!godot!bradley,
  "godot!bradley@mit-eddie"@MIT-XX.ARPA

nessus@mit-eddie.UUCP (Doug Alan) (06/11/84)

Yes.  And if you're too lazy to do a quick sort or merge sort or some
n*log(n) sort (though it shouldn't be very difficult) you could at LEAST
do a straight insertion sort which is just as easy as a bubble sort or
selection sort and always as fast or faster.
-- 
				-Doug Alan
				 mit-eddie!nessus
				 Nessus@MIT-MC

				"What does 'I' mean"?

 

dave@utcsrgv.UUCP (Dave Sherman) (06/12/84)

[what is this discussion doing in net.sources?]

If you really want to understand n*log(n) sorting techniques,
get hold of the computer-generated film "Sorting Out Sorting"
(Univ. of Toronto, 1981). It's available from the U of Toronto
Media Centre, and many university CS departments have purchased
copies. It uses animation to make quicksort, heapsort and others
easy to understand, and demonstrates (via "races" on many items)
how much better n*log(n) is than n-squared.

Dave Sherman
-- 
 {allegra,cornell,decvax,ihnp4,linus,utzoo}!utcsrgv!dave

wm@tekchips.UUCP (Wm Leler) (06/22/84)

I heartily second the recommendation for "Sorting out Sorting".
An excellent film.  An excerpt from it was on one of the
Siggraph tapes as well.

				Wm Leler
				tektronix!tekchips!wm