Hi Tom,
You wrote to David Noon:
TT>TT>for (i1=0; i1TT>   for (i2=i1; i2TT>      if (elem[i1]>elem[i2])
As there is no need to compare an element with itself you can remove a
redundant check from the start of the inner loop and a redundant outer
loop by changing the loop parameters to:
for (i1=0; i1elem[i2])
TT> DN> This is _guaranteed_ to perform n**2 comparisons, even when the
TT> DN> data are already ordered.
TT>Really ? Please explain that one to me...
TT>It seems to me like it would perform 1/2 * (n + 1) * n compares.
Indeed it does :-)
TT>For example, take an array containing 5 elements.
TT>The first loop will cause 5 compares.
TT>The second loop will cause 4 compares.
TT>The third loop will cause 3 compares.
TT>The fourth loop will cause 2 compares.
TT>The fifth loop will cause 1 compare.
TT>--------------------------------------
TT>Total number of compares: 5 + 4 + 3 + 2 + 1 = 1/2 * (5 + 1) * 5 = 15
With my change the total number of compares for 5 elements is
4 + 3 + 2 + 1 = 10, or 1/2 * n * (n-1) which can be re-arranged
to 1/2 * n**2 - n.
This is the number of compares Knuth gets in his analysis of "Straight
Selection sort", which has the same loop construct (page 141 of Vol 3).
So we have the support of a published analysis :-)
This is also the upper bound (or without the early exit flag the actual
number) of compares in bubble sort.
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------