In a message dated 01-12-98, Michael Rathburn said to All about Sort
Algorithm
Hi Michael,
MR>Can someone explain how this sort works I have tried to follow it but I
MR>just get confused.
[snip]
MR>this is the confusing part :-
MR>        while(test == 0)
MR>        {
MR>                test = 1;
MR>                for (i = 0; i < (MAX - 1); i++)
MR>                {
MR>                        if (table[i] < table[i + 1])
MR>                        {
MR>                                temp = table[i];
MR>                                table[i] = table[ i + 1];
MR>                                table[i + 1] = temp;
MR>                                test = 0;
MR>                        }
MR>                }
MR>        }
The simplest response is that it sorts very, very s-l-o-w-ly. This is a
bubble sort.
The while(test == 0) loop keeps the sort looping until the flag variable
'test' fails to keep its change to 1 that immediately follows. This failure
happens whenever an exchange occurs inside the if() statement, inside the
for() loop. Thus, the loop keeps looping until no more exchanges have been
made.
Since the criterion for an exchange is that 2 adjacent elements are out of
sorted sequence, no exchanges means that everything is in sorted sequence.
Then the loop exits, as the array is sorted.
Note that bubble sort is offered by Knuth, and several others, as by far the
worst sorting algorithm around. The next step up is insertion sort, which
typically runs twice as fast. The "great all-rounder" is Shell's algorithm.
The "formula 1 racer" is Hoare's algorithm (usually very fast, but is prone
to breaking down). The "status symbol" of sorting is Batcher's algorithm.
However, C++ programmers are usually renowned for their ignorance of sorting
algorithms, so this thread could be too enlightening to be on-topic in this
echo. I suggest we move it to Pgmrs, where algorithms in general are
on-topic.
Regards
Dave

___
 * MR/2 2.25 #353 * They'll release Windows 97 when NT 4.0 finishes loading.
--- Maximus/2 3.01
---------------