---------------

FIDO MESSAGE AREA==> TOPIC: 239 C LANGUAGE    Ref: F5G00407 Date: 04/24/98
From: JOHN RICHARDSON                                       Time: 10:17am
\/To: BILL BIRRELL                                        (Read 1 times)
Subj: Nested loop

Hi Bill,
 >  while(j > i) putchar('F' - j--);
 >  Decrementing to 0 is slightly more efficient on the PC. :-)
But the extra subtraction provides a cancel to this improved efficiency. 
:) 
John.
--- JetMail 0.99beta23
 * Origin: The Dysfunctional Refrigerator (fidonet 2:2502/60)
---------------

FIDO MESSAGE AREA==> TOPIC: 239 C LANGUAGE    Ref: F5G00408 Date: 04/26/98
From: CHRISTOPHER BUTLER                                    Time: 05:07pm
\/To: HERMAN SCHONFELD                                    (Read 1 times)
Subj: Event Handler

Hi Herman!
Hey, Herman wasn't it you that was talking about Event Handler on 24 Apr 98? 
Yeah... you were talking to Christopher Butler, weren't you?
 HS>> You believe? I KNOW that mainstream compilers have it .. Watcom,
 HS>> Borland, Djgpp, etc. If a compiler doesn't have it, then it most
 HS>> likely contains an equivalent.
 CB>> There is /no/ cprintf call for Unix though..
 CB>> All of those "mainstream" compilers you have mentioned are for
 CB>> MS-DOS...
 HS> Didn't I make it quite clear that cprintf() would be useless outside
 HS> DOS?
So by your logic, there are no "mainstream" compilers for Unix?
Since Unix is a major platform, based a lot on C, you should really try to 
make code portable to Unix.
Chris Butler <chrisb@sandy.force9.co.uk>
--- FMail/386 1.22
 * Origin: ... The Death Butler BBS, +44-1582-620141 ... (2:257/135)
---------------

FIDO MESSAGE AREA==> TOPIC: 239 C LANGUAGE    Ref: F5G00409 Date: 04/26/98
From: DAVID NOON                                            Time: 04:59pm
\/To: BOB STOUT                                           (Read 1 times)
Subj: Liquorice Allsorts

In a message dated 04-24-98, Bob Stout said to David Noon about Liquorice
Allsorts
Hi Bob,
 > Care to add a selection sort to this potpourri?
BS>  Sure, and a heapsort, too, while you're at it! ;-) 
Will do.
Do you want Mergesort and variations [George White and Dominic Battre are
working on these], straight radix sort and radix exchange sort too?
The last 2 are not much use outside of specialised applications, but when
they do work they are comparable in speed to Quicksort with all the fine
tunings. H****n swears by them, but won't post the code.
Regards
Dave
<Team PL/I>
___
 * MR/2 2.25 #353 * He who laughs last uses OS/2.
--- Maximus/2 3.01
 * Origin: DoNoR/2,Woking UK (44-1483-717905)  (2:440/4)
---------------

FIDO MESSAGE AREA==> TOPIC: 239 C LANGUAGE    Ref: F5G00410 Date: 04/26/98
From: DAVID NOON                                            Time: 06:02pm
\/To: CAREY BLOODWORTH                                    (Read 1 times)
Subj: Bubble & Squeak Sorting

In a message dated 04-23-98, Carey Bloodworth said to David Noon about
Bubble & Squeak Sorting
Hi Carey,
DN>We have very recently seen benchmarks in this echo that say that this
DN>assertion is wrong. Very wrong.
CB>Not always.  I had it happen back when I was doing a simple chess
CB>program on an 8 bit micro.  Unusual circumstances, yes, but the point I
CB>was making when I said that the first time was that you can't always go
CB>by the O() notation.
But you were only considering bubble sort against qsort(). There are other
algorithms. There are a few that perform better than bubble sort even on
teensy-weensy datasets of 5 ot 6 elements.
CB>Maybe it was caused by a very poorly implemented quick-sort library
CB>routine, or maybe it was just the very small data set (typically ~30,
CB>but when captures are done, it could be just a few or even 1), but a
CB>bubble sort was measurably, and consistently faster.
CB>I've never, ever said that was typical, but I am very definitely saying
CB>that it _has_ happened.
And I'm saying you didn't consider enough "small dataset" sort algorithms.
CB>All the benchmarks I've seen were for medium data sets.  Thousands of
CB>items.  I haven't seen any that were for small data sets, where the 'O'
CB>of an algorithm (ie: the overhead, and the quality of the
CB>implementation) becomes as, if not more, important than the growth.
The Big-oh and Little-oh notations are difficult to quantify on
medium-to-large datasets, impossible on small ones. They are just too
tendentious. They are more a measure of an abstract algorithm than of an
implementation.
DN>We also have posted routines that are simpler & smaller than bubble sort.
CB>I haven't seen any smaller than bubble sort.
Read on.
CB>A simple bubble sort is
CB>only three lines (or four lines if you like spreading it all out
CB>like I do below).....  It even includes the early out.
Did you see Herman Schonfeld's benchmarks of BUBBLE() and FBUBBLE(). The
latter had the "early exit" flag and was consistently slower, except on
already sorted datasets. The flag's maintenance costs more processing time
than the flag usually saves.
CB>for (a=0,swap=0;a<LAST-1 && swap;a++,swap=0)
CB>  for (b=a+1;b<LAST;b++)
CB>    if (data[b] > data[a])
CB>      {TYPE t=data[a];data[a]=data[b];data[b]=t;swap=1;}
A selection sort with some variations.
It seems you are yet another one who does not actually know how a bubble
sort is coded. Heck, even the much maligned (sp?) Herman got his code right
on this one.
Not all O(n**2) exchange sorts are bubble sorts! [John Gardeniers and
Jonathan de Boyne Pollard please note.]
Here is a _genuine_ bubble sort:
   for (i = n - 1; i > 0; --i)
      for (j = 1; j <= i; ++j)
         if (array[j-1] > array[j])
         {
            Hold_it_here = array[j-1];
            array[j-1] = array[j];
            array[j] = Hold_it_here;
         }
You will note that the comparison is always of _adjacent_ elements. This is
a requirement of the bubble sort algorithm. [A bubble can only float through
the liquid that _immediately_ surrounds it. This is the metaphor that gives
the algorithm its name.] Any decent textbook on algorithmics will explain
this to you.
Moreover, the performance characteristics of bubble sort and selection sort
differ quite markedly, even though both are O(n**2). This is why precise
naming conventions are important. You cannot simply say "This is a bubble
sort because that's the way I've always coded it," when, in fact, it is not
a bubble sort at all. All too many alleged bubble sorts, in this echo,
perform slightly better than expected because the allegations are false.
CB>Frankly, there isn't anything shorter than that, or easier to write from
CB>the ground up, from just memory, in 15 seconds.
How about Insertion sort?
   for (i = 1; i < n; ++i)
   {
      Hold_it_here = array[i];
      for (j = i; j > 0 && array[j-1] > Hold_it_here; --j)
         array[j] = array[j-1];
      array[j] = Hold_it_here;
   }
Scrunch up the code with a text editor and it will be shorter than your
selection sort, and shorter than bubble sort. It is also faster than either
bubble sort or selection sort, even on _very_ small arrays. You will note
that the inner loop has only 1 statement (a move), not 4 (1 comparison & 3
moves).
CB>In that same 15 seconds, I can't even reach for and find Qsort in my C
CB>ref book to find out the exact parameter casts etc. that I need to use
CB>with a qsort compare function.
Who uses qsort()? I don't. [Inmates of the C_PlusPlus echo will, by now,
know why.]
Regards
Dave
<Team PL/I>
___
 * MR/2 2.25 #353 * Windows: Veni, vidi, shelfi...
--- Maximus/2 3.01
 * Origin: DoNoR/2,Woking UK (44-1483-717905)  (2:440/4)
---------------

FIDO MESSAGE AREA==> TOPIC: 239 C LANGUAGE    Ref: F5G00411 Date: 04/26/98
From: DAVID NOON                                            Time: 06:11pm
\/To: CAREY BLOODWORTH                                    (Read 1 times)
Subj: Bubble & Squeak Sorting

In a message dated 04-23-98, Carey Bloodworth said to David Noon about
Bubble And Squeak Sorting
Hi Carey,
DN>Well, it helps to keep us clear on the strategies involved if each has a
DN>separate name.
CB>To me, it's not _worth_ knowing.
I like to know what to avoid.
CB>Let's face it, for 'typical' situations, how many O(N^2) sorts do you
CB>really need to know???!
One: Insertion sort.
DN>Actually, selection sort has a useful place in the world 
DN>when the cost of an
CB>Every sort has at least 1 useful place.
I wouldn't go that far, unless you include the bit bucket.
CB>But that doesn't really mean
CB>it's worth every programmer intimately knowing every one of them.
One should be able to recognize a specific algorithm, at least of the most
common ones, if one is a professional.
CB>If you've got an unusual situation, then it's worth hunting around.  But
CB>for most situations, 'good enough' is good enough.
Are you a Microsoft employee?
DN>Not all O(n**2) algorithms are bubble sorts. More is the pity. Too many
DN>other sort algorithms are also O(n**2).
CB>No, they aren't all bubble sorts.  Doesn't matter squat, because as I
CB>said above, it's still the same dung eating N^2 growth, and they do look
CB>similar.
They don't look very similar around the if-statement. This is crucial to the
way the algorithm performs.
CB>(You shouldn't be able to change two lines and call it a
CB>new algorithm....)
One line is enough if it makes a change in the characteristics of the
algorithm.
CB>It's good enough to just lump them all into the same
CB>group and then go looking for something that's truly better.  If you
CB>even need it.
I agree with the search for something better. By and large, I have found it.
Regards
Dave
<Team PL/I>
___
 * MR/2 2.25 #353 * Life is short. Eat dessert first.
--- Maximus/2 3.01
 * Origin: DoNoR/2,Woking UK (44-1483-717905)  (2:440/4)
---------------

FIDO MESSAGE AREA==> TOPIC: 239 C LANGUAGE    Ref: F5G00412 Date: 04/26/98
From: DAVID NOON                                            Time: 09:13pm
\/To: HERMAN SCHONFELD                                    (Read 1 times)
Subj: Tattslotto Simulator

Hi Herman,
As promised, I created a benchmark program to compare the Shellsort you
copied from Dennis Ritchie with the one I plagiarised from Robert Sedgewick.
Here is the pseudo-random number generator I wrote, as the rand() function
supplied with C Standard library typically loops after 32,766 uses. This one
goes for 2,147,483,646 before returning. The specific algorithm is one of
IBM's dating back to System/360 days.
It was compiled as RANDOM.LIB using Watcom C/C++ 11.0a to create 32-bit OS/2
object code, with default libraries suppressed. [They get filled in later.]
============================== RANDOM.H ====================================
#ifndef PRNG_INCLUDED
#define PRNG_INCLUDED
/* Pseudo-random number generator functions.                    */
/* Copyright (C) 1998, David W. Noon                            */
/* All rights reserved.                                         */
/* You may use this code freely. You may also distribute this   */
/* code provided no charge is levied beyond the price of its    */
/* distribution medium.                                         */
/* The author makes no warranty of the code's usefulness for    */
/* any purpose,and accepts no responsibility for any damages    */
/* caused by its misuse.                                        */
#ifdef __cplusplus
extern "C" {
#endif
/* Random fraction, 0 <= ranfrac() < 1 */
double ranfrac(void);
/* Random integer in the range 1..n */
unsigned int irandom(unsigned int n);
/* Set the seed to a user-supplied value */
void set_seed(unsigned long new_seed);
/* Allow the user to query the seed */
unsigned long get_seed(void);
/* Use time-of-day to randomise the seed. */
void randomise(void);
#ifdef __cplusplus
} /* extern "C" */
#endif
#endif
============================== RANDOM.C ====================================
/* Simple pseudo-random number generator.                       */
/* Uses a multiplicative congruence method.                     */
/* Copyright (C) 1998, David W. Noon                            */
/* All rights reserved.                                         */
/* You may use this code freely. You may also distribute this   */
/* code provided no charge is levied beyond the price of its    */
/* distribution medium.                                         */
/* The author makes no warranty of the code's usefulness for    */
/* any purpose,and accepts no responsibility for any damages    */
/* caused by its misuse.                                        */
/* Watcom's <dos.h> works for OS/2 and NT too. */
#include <dos.h>
/* Simple pseudo-random number generator */
static unsigned long iseed = 13579UL;
/* Random fraction, 0 <= ranfrac() < 1 */
double ranfrac(void)
{
   iseed = (iseed*950706376UL)%2147483647UL;
   return iseed/2.147483647e+9;
}
/* Random integer in the range 1..n */
unsigned int irandom(unsigned int n)
{
   iseed = (iseed*950706376UL)%2147483647UL;
   return (iseed%n) + 1U;
}
/* Set the seed to a user-supplied value */
void set_seed(unsigned long new_seed)
{
   iseed = new_seed | 1UL; /* Ensure it's odd */
   return;
}
/* Allow the user to query the seed */
unsigned long get_seed(void)
{
   return iseed;
}
/* Use time-of-day to randomise the seed. */
void randomise(void)
{
   struct dostime_t Now;
   /* Obtain time-of-day to 1/100 sec. */
   _dos_gettime(&Now);
   /* Calculate hundredths of seconds from midnight. */
   iseed = (((Now.hour*60 + Now.minute)*60 + Now.second)*100
         + Now.hsecond) | 1UL;
   return;
}
============================================================================
Regards
Dave
<Team PL/I>
___
 * MR/2 2.25 #353 * 186,000/mps.  It's not just a good idea.  It's the law.
--- Maximus/2 3.01
 * Origin: DoNoR/2,Woking UK (44-1483-717905)  (2:440/4)
---------------

FIDO MESSAGE AREA==> TOPIC: 239 C LANGUAGE    Ref: F5G00413 Date: 04/26/98
From: DAVID NOON                                            Time: 09:34pm
\/To: HERMAN SCHONFELD                                    (Read 1 times)
Subj: Your Gap Is Too Tight!

Hi Herman,
Here is the benchmark program for the two versions of Shellsort. It requires
the PRNG [RANDOM.LIB] that I sent you in a separate message.
================================ SHELLGAP.C ================================
/* Program to test the performance characteristics of different */
/* gap selections for Shell's sorting algorithm.                */
/* Copyright (C) 1998, David W. Noon                            */
/* All rights reserved.                                         */
/* You may use this code freely. You may also distribute this   */
/* code provided no charge is levied beyond the price of its    */
/* distribution medium.                                         */
/* The author makes no warranty of the code's usefulness for    */
/* any purpose,and accepts no responsibility for any damages    */
/* caused by its misuse.                                        */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
/* Our 31-bit pseudo-random number generator */
#include "random.h"
#ifdef __WATCOMC__
#pragma off(unreferenced)
#pragma on(reuse_duplicate_strings)
#endif
/* Shellsort into ascending order using a gap == 1 mod 3. */
static void RobertSedgewick(double array[], int n)
{
   int h, i, j, t, const mul = 3;
   double Hold_it_here;
   if (n > 1)
   {
      h = mul + 1;
      while (h <= n)
         h = h*mul + 1;
      do
      {
         h /= mul;
         for (i = h; i < n; ++i)
         {
            Hold_it_here = array[i];
            j = i;
            for (t = j - h; array[t] > Hold_it_here; t -= h)
            {
               array[j] = array[t];
               j = t;
               if (j < h)
                  break;
            }
            array[j] = Hold_it_here;
         }
      } while (h > 1);
   }
   return;
}
/* Shellsort into ascending order using a bisection gap. */
static void DennisRitchie(double array[], int n)
{
   int h, i, j, t;
   double Hold_it_here;
   for(h = n/2; h > 0; h /= 2)
   {
      for (i = h; i < n; ++i)
      {
         Hold_it_here = array[i];
         j = i;
         for (t = j - h; array[t] > Hold_it_here; t -= h)
         {
            array[j] = array[t];
            j = t;
            if (j < h)
               break;
         }
         array[j] = Hold_it_here;
      }
   }
   return;
}
/* Subroutine to build an already sorted array */
void Build_sorted(double array[], unsigned long n)
{
   unsigned long i;
   /* An already sorted sequence */
   for (i = 0UL; i < n; ++i)
      array[i] = i + ranfrac();
}
/* Subroutine to build an array in reverse order */
void Build_reversed(double array[], unsigned long n)
{
   unsigned long i;
   /* A reversed sequence */
   for (i = 0UL; i < n; ++i)
      array[i] = n - i + ranfrac();
}
/* Subroutine to build an array in random order */
void Build_random(double array[], unsigned long n)
{
   unsigned long i;
   /* A random sequence */
   for (i = 0UL; i < n; ++i)
      array[i] = (ranfrac() - .5)*2e3;
}
/* Function to calibrate memcpy() overhead */
unsigned long Calibrate_copy(const double array[], size_t array_size,
      unsigned long ntimes)
{
   double * Work_array;
   clock_t Start_time;
   unsigned long overhead, i;
   Work_array = malloc(array_size);
   if (Work_array == NULL)
   {
      fputs("Calibrate_copy:\n",stderr);
      fprintf(stderr,"Unable to allocate array of size %lu.\n",
            (unsigned long) array_size);
      return 0xFFFFFFFFUL;
   }
   Start_time = clock();
   for (i = ntimes; i > 0UL; --i)
      memcpy(Work_array,array,array_size);
   overhead = clock() - Start_time;
   /* Release storage */
   free(Work_array);
   return overhead;
}
/* Run the selected sort routine a given number of times */
unsigned long Run_sort(const double Base_array[], int nelems,
      unsigned long ntimes, void (* sort_it)(double [], int))
{
   double * Work_array;
   unsigned long i, nclocks;
   const size_t array_size = nelems*sizeof(double);
   clock_t Start_clock;
   Work_array = malloc(array_size);
   /* Not enough memory? */
   if (Work_array == NULL)
   {
      fputs("Run_sort:\n",stderr);
      fprintf(stderr,"Unable to allocate array of size %lu.\n",
            (unsigned long) array_size);
      return 0xFFFFFFFFUL;
   }
   Start_clock = clock();
   for (i = ntimes; i > 0UL; --i)
   {
      /* Refresh array to original */
      memcpy(Work_array,Base_array,array_size);
      /* Run selected sort */
      sort_it(Work_array,nelems);
   }
   nclocks = clock() - Start_clock;
   /* Release storage */
   free(Work_array);
   return nclocks;
}
#define SIZES 7UL
int main(void)
{
   static const unsigned short array_elems[SIZES] =
         {10U,50U,100U,500U,1000U,5000U,10000U};
   unsigned long i, Herman_time[SIZES][3], Gardner_time[SIZES][3];
   /* Set a fixed seed for our PRNG */
   set_seed(54321UL);
   /* Run the benchmark for each array size */
   for (i = 0UL; i < SIZES; ++i)
   {
      const size_t array_size = array_elems[i]*sizeof(double);
      const unsigned long iters = 50000UL/array_elems[i];
      unsigned long Copy_overhead;
      double * Base_array;
      Base_array = malloc(array_size);
      if (Base_array == NULL)
      {
         fprintf(stderr,"Unable to allocate Base_array of size %u.",
               array_elems[i]);
         return 255;
      }
      /* Calibrate copy overhead */
      Copy_overhead = Calibrate_copy(Base_array,array_size,iters);
      /* Benchmark on already sorted array */
      Build_sorted(Base_array,array_elems[i]);
      Herman_time[i][0] = Run_sort(Base_array,array_elems[i],iters,
            DennisRitchie) - Copy_overhead;
      Gardner_time[i][0] = Run_sort(Base_array,array_elems[i],iters,
            RobertSedgewick) - Copy_overhead;
      /* Benchmark on reversed array */
      Build_reversed(Base_array,array_elems[i]);
      Herman_time[i][1] = Run_sort(Base_array,array_elems[i],iters,
            DennisRitchie) - Copy_overhead;
      Gardner_time[i][1] = Run_sort(Base_array,array_elems[i],iters,
            RobertSedgewick) - Copy_overhead;
      /* Benchmark on random array */
      Build_random(Base_array,array_elems[i]);
      Herman_time[i][2] = Run_sort(Base_array,array_elems[i],iters,
            DennisRitchie) - Copy_overhead;
      Gardner_time[i][2] = Run_sort(Base_array,array_elems[i],iters,
            RobertSedgewick) - Copy_overhead;
      /* No memory leakage. */
      free(Base_array);
   }
   /* Print results */
   puts("All timings are in clocks.\n\nBisection gap:");
   puts("+---------+----------------+----------------+----------------+\n"
        "|   No.   | Already sorted |    Reversed    |     Random     |\n"
        "+---------+----------------+----------------+----------------+");
   for (i = 0UL; i < SIZES; ++i)
      printf("| %7u | %14lu | %14lu | %14lu |\n",array_elems[i],
            Herman_time[i][0],Herman_time[i][1],Herman_time[i][2]);
   puts("+---------+----------------+----------------+----------------+");
   puts("\n\nGap == 1 mod 3:");