Hi Tom,
You wrote to David Noon:
TT>JG> Please post an example of how you would write a bubble
TT>JG> sort.
TT> DN> /* Bubble sort into ascending order */
TT> DN> void ascending(double array[], int n)
TT> DN> {
TT> DN>    int i,j;
TT> DN>    double Hold_it_here;
TT> DN>    for (i = n - 1; i > 0; --i)
TT> DN>       for (j = 1; j <= i; ++j)
TT> DN>          if (array[j-1] > array[j])
TT> DN>          {
TT> DN>             Hold_it_here = array[j-1];
TT> DN>             array[j-1] = array[j];
TT> DN>             array[j] = Hold_it_here;
TT> DN>          }
TT> DN>    return;
TT> DN> }
TT>Strange... I always write my bubble sorts this way: (yes, I
TT>use bubble sort for everything that's small enough and not
TT>time critical)
TT>for (i1=0; i1{
TT>   for (i2=i1; i2   {
TT>      if (elem[i1]>elem[i2])
TT>      {
TT>         tmp = elem[i1];
TT>         elem[i1] = elem[i2];
TT>         elem[i2] = tmp;
TT>      }
TT>   }
TT>}
TT>Am I perhaps mistaking this loop for a bubble sort ? If so,
TT>what's the name of this sort (sic) of algorithm ? (I'm not
TT>a sorting expert; usually either this or quicksort works
TT>for me)
It's not a "bubble sort", that (as in David's code above which is)
compares ajacent pairs and swaps whenever necessary.
It looks similar to what Knuth calls a Selection sort, but you are doing
extra intermediate swaps which will make it slower than a true selection
sort. See page 141 of Knuth Vol 3.
An implementation of Knuth's "Straight Selection" sort (page 140 of
Knuth, Vol 3) would be:
select (short elem[],int limit)
{
int offset,i1,i2;
short tmp;
for (i1=0; i1elem[i2])
      offset = i2;
  if (offset != i1)
    {
    tmp = elem[i1];
    elem[i1] = elem[offset];
    elem[offset] = tmp;
    }
  }
}
Oh btw, my code Public Domain, etc.
To keep David happy, some comparative timings:
Tests for short integer data normalised to 1000 repeats in clock() ticks.
Set    quickersort|  bubble     |  Insertion  |  Tom's Sort |  Selection
Size Rand Sort Rev Rand Sort Rev Rand Sort Rev Rand Sort Rev Rand Sort Rev
250    5    0    1   84   46 110   34    0  68   80   47 102   47   47  47
125    2    0    0   20   11  27    8    0  17   19   11  25   12   11  12
 62    0    0    0    5    2   6    2    0   4    4    2   6    2    2   2
 31    0    0    0    1    0   1    0    0   0    1    0   1    0    0   0
I have to run the tests with larger data sets than would normally be used
to get timings that show the differences between sorts. Fast processors
occasionally have their drawbacks...
Rand = a set of random data - the same for all runs
Sort = The sorted version of the random data
Rev  = The sorted data reversed
Quickersort - A version of the SNIPPETS qsort() for integral data types
bubble      - The bubble sort David posted (above) changed to shorts
Insertion   - The insertion sort David posted changed to shorts
Tom's sort  - Your code above
Selection   - My code above
Compiler: BC 3.1
System Intel P133 in HX motherboard
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------