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.ARPAnessus@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!davewm@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