Hi David,
You wrote to me:
DN>DN>Ugh! That has even more iterations than genuine bubble sort.
DN>GW>You can't count! It has _exactly_ the same number :-)
DN>I don't think so. Bubble sort's inner loop is bounded by the current index
DN>of the outer loop. Tom's algorithm always uses the upper bound of the 
rray
DN>for the inner loop, even when the outer loop's index is a 0.
Sure it is, but you _still_ can't count :-). Bubble sort always starts
the inner loop from zero (things bubble _up_) and decrements the upper
bound, while Toms increments the start of the inner loop (things are
moved _down_) and retains the upper bound. Tom has an error in the
initialisation of the inner loop, it should be the outer loop value + 1,
and the outer loop should terminate one earlier too...
DN>DN>This is _guaranteed_ to perform n**2 comparisons, even when the data 
re
DN>DN>already ordered. That is twice as slow as bubble sort's worse case.
DN>GW>It also performs the same number of comparisons! :-)
DN>No. Same again, since it is 1 comparison per iteration.
See above :-).

DN>GW>Or even the version in SNIPPETS, which takes the same parameter list as
DN>GW>the standard library qsort().
DN>But calling a function to do comparisons is one of the things that slows
DN>down qsort(), whatever the internal algorithm. That is why I would never 
use
DN>qsort() or a clone, but would instantiate the template.
But for generalised sorting a struct on two separate keys, or of two
related but distinct sets of data, being able to change the comparison
routine (see code ) or replace the swap routine has much going for it.
Mind you, sorting data on two separate keys is the _major_ limitation of
quicksort, as it does _not_ keep items with the same key in the same
order as in the original data. So, if sorting data on two or more keys,
a different sort is required and neither quicksort or Shellsort are
suitable (but insertion sort is ).
Code? Oh! Yes :-)
Here is a demonstration test harness using the SNIPPETS sorts :-)
/*
        Copyright 1998 G. White
        Code donated to the Public Domain, use as you will.
    Normally generates a set of test data, one element of which is the
    initial sequence.
    The object is to get the data sorted with index as the primary sort,
    key as the secondary sort (all items with the same index to have
    key in sequence) and keeping all data with the same index and key
    in the initial sequence.
    So for each sort tested the data is first sorted on key and then on 
ndex.
    The test functions check the sorted data for conformance with the
    requirements and normally the number of out of sequence elements
    is displayed.
    If the output is re-directed to a file an expanded output to the
    file shows the out of sequence data pairs.
    Portability: fstat() is POSIX but not ANSI.
*/
/* sort test harness */
#include 
#include 
#include 
#include 
#include 
#include "snipsort.h"
#define DATA_SIZE 4000  /* Make this smaller to speed things up */
#define TEST_END        30
int     compare_index (const void *a,const void * b);
int     compare_key (const void *a,const void * b);
int     check_data (int sort_len);      /* Counts the sequence errors */
void    show_diff (int sort_len);       /* Shows the sequence errors */
struct  test_struct {
        short   key;
        short   index;
        short   sequence;
        };
struct test_struct ref_strct[DATA_SIZE];
struct test_struct sort_strct[DATA_SIZE];
int main (void)
{
int     counter,sort_len,redir = 0;
struct  stat    file_stat;
time_t  curr_time;
fstat (fileno (stdout),&file_stat);
if (file_stat.st_mode & S_IFREG)
    redir = 1;
sort_len = DATA_SIZE;
if (redir)
    printf ("\n\nData generated on %s",ctime (&curr_time));
/* Set up the initial data */
for (counter = 0;counter < sort_len;counter++)
    {
    ref_strct[counter].key = rand ()/100;
    ref_strct[counter].index = rand ()/100;
    ref_strct[counter].sequence = counter;
    }
printf ("\n\nStructure sort tests.");
do
    {
    printf ("\n %5d ",sort_len);
/* Set up data to be sorted */
    memcpy (sort_strct,ref_strct,sort_len * sizeof (ref_strct[0]));
    if (redir)
        printf ("\nQsort");
    else
        printf (" Qsort");
    qsort (sort_strct,sort_len,sizeof (sort_strct[0]),compare_key);
    qsort (sort_strct,sort_len,sizeof (sort_strct[0]),compare_index);
    printf (" %4d seq",check_data (sort_len));
    if (redir)
        {
        show_diff (sort_len);
        printf ("\nShellsort");
        }
    else
        printf (" Shellsort");
>>> Continued to next message
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------