Hi David,
You wrote to me:
DN>At last, another actual programmer. ... =8*)
Yes, there are some of us about :-)
DN>GW>To keep David happy, some comparative timings:
DN>Right chuffed! ... :-)
:-)
DN>GW>Tests for short integer data normalised to 1000 repeats in clock() 
ticks.
DN>GW>Set    quickersort|  bubble     |  Insertion  |  Tom's Sort |  
election
DN>GW>Size Rand Sort Rev Rand Sort Rev Rand Sort Rev Rand Sort Rev Rand 
SortRev
DN>GW 250    5    0    1   84   46 110   34    0  68   80   47 102   47  47  
47
DN>GW>125    2    0    0   20   11  27    8    0  17   19   11  25   12  11  
12
DN>GW> 62    0    0    0    5    2   6    2    0   4    4    2   6    2    2  
2
DN>GW> 31    0    0    0    1    0   1    0    0   0    1    0   1    0    0  
0
DN>I am a little surprised that Tom's sort was marginally faster than bubble
DN>sort, but I see why a bit further down.
DN>I also note the omission of Shellsort. ... :-(
Purely on space grounds, that was just a comparison of the slower
sorting routines and all I could fit on a line...
DN>[snip]
DN>GW>Compiler: BC 3.1
DN>And now we see why that bubble sort was slower. The old Borland compiler 
did
DN>not optimise the computation of j-1 in its repeated usage in the 
omparison
DN>and exchange.
No, that's not the only reason, though it may be a contributary factor.
Tom's code can do fewer swaps (in my tests its equal or fewer).
Timings, code modified to count and return number of data swaps.
The figure in brackets is the the number of swaps for the data set.
Timing data generated on Wed Apr 08 08:46:37 1998
Tests for short integer data normalised to 1000 repeats in clock() ticks.
Set Size             bubble                            Tom's Sort
         Rand         Sort        Rev        Rand         Sort       Rev
 250   90(15782)   46(    0)  123(31123)   87(15714)   46(    0)  115(30735)
 125   22( 3764)   11(    0)   30( 7750)   21( 3764)   11(    0)   28( 7750)
  62    5(  982)    2(    0)    7( 1891)    5(  982)    2(    0)    7( 1891)
  31    1(  244)    0(    0)    1(  465)    1(  244)    0(    0)    1(  465)
Sorted data disturbed.
Set Size             bubble                            Tom's Sort
         Rand         Sort        Rev        Rand         Sort       Rev
 250   90(15782)   55( 3098)  117(28025)   87(15714)   55( 3088)  110(27647)
 125   22( 3764)   13(  805)   29( 6945)   21( 3764)   13(  805)   27( 6945)
  62    5(  982)    3(  206)    7( 1685)    5(  982)    3(  206)    6( 1685)
  31    1(  244)    0(   82)    1(  383)    1(  244)    0(   82)    1(  383)
Last 10% of Sorted data random.
Set Size             bubble                            Tom's Sort
         Rand         Sort        Rev        Rand         Sort       Rev
 250   90(15782)   54( 2654)  118(28462)   87(15714)   53( 2494)  110(27941)
 125   22( 3764)   13(  749)   29( 7199)   21( 3764)   13(  722)   27( 7159)
  62    5(  982)    3(  119)    6( 1695)    5(  982)    3(  114)    6( 1690)
  31    1(  244)    0(   31)    1(  418)    1(  244)    0(   30)    1(  417)
Run Completed: Wed Apr 08 08:51:59 1998
DN>Everybody in this echo, even lurkers, should now face towards Scott's
DN>Valley, California, and shout profanities at the compiler developers at
DN>Borland.
Why bother, I stopped upgradeing with 3.1. But it is good enough for the
code that currently brings in money and for various reasons I can't
justify the work in porting it to Watcom (it uses a few Borlandisms in
the display routines).
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------