Hi David,
You wrote to John Gardeniers:
DN>JG> Please post an example of how you would write a bubble
DN>JG> sort.
DN>/* Bubble sort into ascending order */
DN>void ascending(double array[], int n)
DN>{
DN>   int i,j;
DN>   double Hold_it_here;
DN>   for (i = n - 1; i > 0; --i)
DN>      for (j = 1; j <= i; ++j)
DN>         if (array[j-1] > array[j])
DN>         {
DN>            Hold_it_here = array[j-1];
DN>            array[j-1] = array[j];
DN>            array[j] = Hold_it_here;
DN>         }
DN>   return;
DN>}
DN>I have left out the "early exit" flag, as was in the version posted by
DN>Michael Rathburn. The above is the "pure" algorithm [in all its glory].
DN>For an academic reference, see page 101 of Professor Sedgewick's book I
DN>mentioned in my message to Herman Schonfeld in this echo a day or two ago.
Or pages 106 to 111 of Knuth, Vol 3, first edition.
DN>JG> I feel you must be
DN>JG> doing something very wrong to warrant such a statement.
DN>Can you see an error in my code? I have to confess I haven't coded a 
ubble
DN>sort in many years.
Looks correct to me :-)
DN>Well, here is insertion sort for you to look at:
DN>/* Insertion sort into ascending order */
DN>void ascending(double array[], int n)
DN>{
DN>   int i, j;
DN>   double Hold_it_here;
DN>   for (i = 1; i < n; ++i)
DN>   {
DN>      Hold_it_here = array[i];
DN>      for (j = i; j > 0 && array[j-1] > Hold_it_here; --j)
DN>         array[j] = array[j-1];
DN>      array[j] = Hold_it_here;
DN>   }
DN>   return;
DN>}
DN>As you can see, Insertion sort has only 1 move in its innermost loop. 
Bubble
DN>sort has 0 or 3 depending on the results of the comparison. Moreover, 
"early
DN>exit" is an intrinsic part of Insertion sort's inner loop, without the 
eed
DN>for setting and testing a flag variable. Care to comment about it now?
Knuth's comment (page 110): "Compared to straight insertion (Algoritm
5.2.1S), bubble sorting requires a more complicated program and takes
about twice as long!"
DN>JG> BTW, never
DN>JG> compare sorts unless you also specify the exact conditions under which
DN>JG> you're making the comparison.
DN>I always benchmark algorithms using the same test datasets.
Me too :-)
DN>JG> Please define "typically".
DN>How about "all the time" in this case? See my message to Auke providing
DN>running times for these 2 algorithms. However, simple inspection of the 
code
DN>should show you why Insertion sort is almost invariably faster.
DN>JG> For
DN>JG> more than  100 items I would never use either the bubble or insertion.
DN>Neither would I. I would not use them for more than 8. If you look at the
DN>Quickersort template I posted in the C_PlusPlus echo you will see the
DN>theshold I used for switching between Hoare's algorithm and Insertion 
rt.
Seconded (though maybe I'd go up to 10 items).
DN>JG> Come to think of it, I can't imagine a situation where I *would* use 
the
DN>JG> insertion sort, in any  of it's forms.
DN>Well, since its inner loop is only 1/3 the size of bubble sort's, you 
should
DN>consider it for small arrays.
And it's faster...
DN>JG> I have a very simple rule, which has served me well for
DN>JG> decades. For situations
DN>JG> where the number of items are known to be no more than about 100 I use
DN>JG> the bubble sort, unless speed is crucial, in which case the sort will 
be
DN>JG> selected intelligently at run time.
DN>Well, I still refuse to use bubble sort. Just look at the code above.
Seconded :-)
DN>I use Shellsort as my default, since it deflates automatically into
DN>Insertion sort for small arrays.
And so does quick sort and it's derivatives.
DN>JG> For larger numbers of items I use a
DN>JG> Shell-Metzner, which my testing has shown to be distinctly the fastest
DN>JG> _on_average_ when tested under varying conditions.
DN>And Shell-Metzner is a spruced up Insertion sort, since it is based on
DN>Donald Shell's algorithm. So you _do_ use a variant of Insertion sort.
DN>JG> In actual use I have
DN>JG> never had the kind of specialised situation in which any other sort 
ad
DN>JG> noticeable advantage.
DN>Shell's improvements on Insertion sort do make that algorithm the "great
DN>all-rounder".
DN>JG> It might also be worth mentioning that a Quicksort isn't. For that
DN>JG> reason I have never used, and never expect to use, qsort().
DN>If you read the C_PlusPlus echo, you will read something about that very
DN>topic. You might also be able to deduce whether or not I ever bother with
DN>qsort(). ... :-)
My test timings were instructive. With all the speed ups a quickersort
is faster than shellsort except where the data is close to ordered, and
even then it isn't too far behind. Your code as posted in the template
in C_Plusplus would be very slow on close to ordered data because the
test key you use brings it back to N^2 time. Using R. C. Singleton's
method of selecting the median of the left, right and center elements as
test key improves peformance significantly in this case (and improves it
in general as well ).
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------