Hi David,
You wrote to Michael Rathburn:
DN>MR>Can someone explain how this sort works I have tried to follow it but I
DN>MR>just get confused.
DN>[snip]
DN>MR>this is the confusing part :-
DN>MR>        while(test == 0)
DN>MR>        {
DN>MR>                test = 1;
DN>MR>                for (i = 0; i < (MAX - 1); i++)
DN>MR>                {
DN>MR>                        if (table[i] < table[i + 1])
DN>MR>                        {
DN>MR>                                temp = table[i];
DN>MR>                                table[i] = table[ i + 1];
DN>MR>                                table[i + 1] = temp;
DN>MR>                                test = 0;
DN>MR>                        }
DN>MR>                }
DN>MR>        }
DN>The simplest response is that it sorts very, very s-l-o-w-ly. This is a
DN>bubble sort.
About as slow as you can get unless the source data is nearly sorted,
and even then there are better...
DN>The while(test == 0) loop keeps the sort looping until the flag variable
DN>'test' fails to keep its change to 1 that immediately follows. This 
ailure
DN>happens whenever an exchange occurs inside the if() statement, inside the
DN>for() loop. Thus, the loop keeps looping until no more exchanges have been
DN>made.
DN>Since the criterion for an exchange is that 2 adjacent elements are out of
DN>sorted sequence, no exchanges means that everything is in sorted sequence.
DN>Then the loop exits, as the array is sorted.
DN>Note that bubble sort is offered by Knuth, and several others, as by far 
the
DN>worst sorting algorithm around. The next step up is insertion sort, which
DN>typically runs twice as fast. The "great all-rounder" is Shell's 
lgorithm.
DN>The "formula 1 racer" is Hoare's algorithm (usually very fast, but is 
rone
DN>to breaking down). The "status symbol" of sorting is Batcher's algorithm.
I do like Knuth's description of Bubble sort (Vol 3, Page 111) :-).
By "Hoare" you mean what he called "Quicksort" I take it?
Batcher's method is interesting, but why "status symbol"?
DN>However, C++ programmers are usually renowned for their ignorance of 
sorting
DN>algorithms, so this thread could be too enlightening to be on-topic in 
his
DN>echo. I suggest we move it to Pgmrs, where algorithms in general are
DN>on-topic.
Hehehe. I did reading up on sorting during my degree course (not as part
of the course but for a programming project) and as this was before
Knuth I did it through the CACM. I got as far as "Quickersort"
("Quicksort" with a basic sort (Shell/Bubble/exchange? I forget which)
when the partition was less than a few elements long. Batcher's paper
was still (well) in the future then... I've still got the Algol code
around (and possibly tapes or card decks as well).
I'll follow to PGMRS if Michael follows this up.
George
 * SLMR 2.1a * All Trademarks acknowledged (just in case ).
--- Maximus/2 3.01
---------------