From: buhr@daimi.aau.dk (Morten Buhr)
Subject: Re: Bubble Sort Routine
Organization: DAIMI: Computer Science Department, Aarhus University, Denmark
Date: Mon, 5 Oct 92 07:38:29 GMT

mccullou@cae.wisc.edu (Mark McCullough) writes:

>In article <718166419.1@ttlg.ttlg.UUCP> James.MacGregor@ttlg.UUCP (James MacGregor) writes:
>> > From: Dennis.Ayala@f23.n367.z1.FIDONET.ORG (Dennis Ayala)
>> > Newsgroups: comp.lang.pascal
>> > Subject: Bubble Sort Routine
>> > Organization: FidoNet node 1:367/23 - The Wall 1,
>> > Guaynabo PR
>> > Date: Sun, 27 Sep 92 20:30:00 EDT
>>
>> > Hello All:
>>
>> >   If it is possible that somebody would be kind enough
>> > to post a pretty good bubble sort routine I will appreciate
>> > it. I kinda need one.
>>
>> > Greetings,
>>
>> > Dennis Ayala
>>
>>Dennis, without intended offense, the only 'good' bubblesort is a *dead* bubblesort!  If you want a simple-to-code sorting algorithm that's ample for general use, look seriously at using a Shell or (preferably) Shell-Metzner.
>>
>>Bubblesorts tend to have a processing time proportional to the *square* of the number of elements processed (IE: a 10 element list takes 100 time units, a 100 element list takes 10,000 time units!)

>Uh, not to burst your shell, but shell sorts are also a O(n^2) sort.  They 
>simply can take advantage of special situations better than the base bubble
>sort.  Also, for a list with just a few elements out of order, the smart
>bubble sort is one of the better sorts to use, (assuming the elements are
>simply flipped), as it will reflip those elements and quit.  Don't knock the
>bubblesort.  Unless you are dealing with more than 1000 elements in the list
>to be sorted, it normally isn't worth the time to look up a fancier sort.
>Good code also means ease for the programmer and maintainablity.  I have yet
>to see a non-professional programmer comment their code properly to make
>a fancier sort worth it for common programming, but professional programmers
>tend to use Fortran 77.  (What's this C everyone talks about, it is no good
>for math.) ;) >

>>If you are only dealing with a very small number of elements, at least consider making the sorting an integral part of the input routine (IE: using something like an insertion sort); bubble-sorting is only useful as an example of what *not* to do!  :-)

>Turns out most sorts we use today are O(n^2).  Remember what big O notation
>means if you doubt me.  Yea the other sorts are faster, but they differ
>by a constant, and not by a magnitude.  Quick sort is a genuinely faster sort,
>but why bother coding it?  It means you have to look it up, and _proper_
>commenting is a pain.  How many people actually understand each step of a
>quick sort enough to rediscover it?  (Since it was discovered by accident,
>probably only if you really studied it.)  As I remember, the quick sort is
>a O (n lg n).  If you really want something faster, use a hashing table.
   ^^^^^^^^^^
 Quick-sort runs in EXPECTED time O(n*log(n)). That is if the elements is
 randomly inserted in the list you want to sort.
 But in WORST-CASE time, the Quick-sort is also a O(n^2) sort. The worst-
 case is when the elements is inserted ordered in the list.
 The reason for using Quick-sort, is that the constant hidden in the big-O
 notation is VERY small for Quick-sort, compared with the true O(n*log(n))
 sorts, fx Merge-sort, Select-sort etc.

>O (n).  But who wants to waste the memory?  Remember, 100 clock ticks is still
>quite fast.

>As for the original post looking for the code, I would reccomend buying a 
>reasonable book on Computer Science in Pascal.  It should have a whole section
>on sorting and searching.

>:)M^2


/Morten












-- 
Morten Buhr / e-mail buhr@daimi.aau.dk
Computer Science Department 
Aarhus University
Denmark
From: jcrowley@leotech.mv.com (Jon Crowley)
Sender: uucp@leotech.mv.com