Hi Jonathan,
You wrote to me:
JDBP> DN>>>    for (i = n - 1; i > 0; --i)
JDBP> DN>>>       for (j = 1; j <= i; ++j)
JDBP> DN>>>          if (array[j-1] > array[j]) { /* swap j-1 with j */ }
JDBP> TT>> for (i1=0; i1 TT>>   for (i2=i1; i2 TT>>      if (elem[i1]>elem[i2]) { /* swap i2 with i1 */ }
JDBP> GW> It's not a "bubble sort", [...]
JDBP>Yes it is.  I've elided the exchange code in both Tom's and David's 
ode,
JDBP>which should make it clearer that they are, in essence, the
JDBP>same thing, merely processing the array in different
JDBP>directions.  Tom's code is, in fact, closer to the
JDBP>"classic" Bubble Sort that most people think of, since it
JDBP>processes the array in the same direction as the final
JDBP>intended ordering.
No they are _NOT_!!!
David's bubble sort code compares an element with its neighbour, and
swaps them if they are mis-ordered, which is the way a bubble sort
traditionally works. The code then keeps makeing passes through the
code, and knowing that the last search put the extreem element at the
end of the search can reduce the search by one each time, until there
are no exchanges in a search (or, worst case, the end is at the start)
when you are finished.
In a traditional bubble sort, elements sink down slowly, but rise up
quickly. If early exit on no exchanges has been used a modification to
process in alternate directions is sometimes used to reduce the
total number of passes needed and hence the number of comparisons. It
does not change the number of exchanges needed and is beneficial where
there is relatively minor mis-ordering.
Tom's code searches for elements in turn from one end of the array,
looking through the unsorted part of the array to find the next required
element to add to the end of the already sorted part, it is a selection
for the next element. There is no possible early exit (it always
requires 1/2 (n^2 - n) comparisons if you remove his redundant checks).
The operation of Tom's code can be speeded up considerably by not
exchanging the data each time a prospective new next sorted element is
found, but by just saving the offset of the next prospective element,
and doing the exchange at the end of the pass.
JDBP>Given that David has previously bemoaned the fact that all that anyone 
see
JDBP>to do in this echo is post Bubble Sort, I find it ironic
JDBP>and amusing that neither you nor he can actually recognise
JDBP>it when presented with it.  Perhaps echo participants
JDBP>should be encouraged to post Bubble Sort *more often*, so
JDBP>that you two can sharpen your recognition skills.  (-:
But we can...
"Straight insertion" (see Knuth Vol 3, page 81), "bubble" (Knuth page
107) and "straight selection" (Knuth page 139) sorts _all_ share the
same basic loop structures above.
For a sort to be a "bubble sort" it has to compare _ajacent_ pairs of
elements, and exchange them as required (it also leaves the array more
ordered after each pass). If it does anything else it becomes a
different type of sort. So Tom's code is a "selection sort", it selects
the next element required from those remaining (and will normally leave
the array more _disordered_ after the early passes).
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------