Hi All,
Here is the template for Quicksort with 2 refinements over Hoare's original
algorithm:
     i)  Use of Insertion sort for subfiles shorter than a threshold;
    ii)  Singleton's median-of-three pivot selection.
I have also changed the placeholder for the pivot element from a subscript
to a pointer. This will produce slightly better code on most 16-bit systems,
and from some 32-bit compilers too.
============================ quicksrt.hpp ==================================
// Templates for Median-of-three algorithm for ascending & descending sort.
// This is based on Hoare's algorithm, but is a significant improvement.
// It also includes the Quickersort algorithm's usage of Insertion sort
// for short subfiles.
// Copyright (C) 1998, David W. Noon
// All rights reserved.
// You may use this code freely. You may also distribute it, provided
// no charge is levied beyond that for 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.
template void ascending(T array[], int l, int r)
{
   int i, j, const shorty = 8;
   T Hold_it_here;
   if (r > l)
   {
      // If the subfile is short use insertion sort
      if (r - l <= shorty)
      {
         for (i = l + 1; i <= r; ++i)
         {
            Hold_it_here = array[i];
            for (j = i; j > l && array[j-1] > Hold_it_here; --j)
               array[j] = array[j-1];
            array[j] = Hold_it_here;
         }
      }
      else
      {
         T * Pivot_element = &array[l], * Rightmost_element = &array[r];
         // Mid-point of current sub-file
         i = (l + r)/2;
         // Exchange the middle one and the leftmost
         Hold_it_here = *Pivot_element;
         *Pivot_element = array[i];
         array[i] = Hold_it_here;
         // Sort the leftmost, leftmost bar 1 and rightmost
         // such that:  leftmost bar 1 <= leftmost <= rightmost
         i = l + 1; // leftmost bar 1
         if (array[i] > *Rightmost_element)
         {
            Hold_it_here = *Rightmost_element;
            *Rightmost_element = array[i];
            array[i] = Hold_it_here;
         }
         if (*Pivot_element > *Rightmost_element)
         {
            Hold_it_here = *Rightmost_element;
            *Rightmost_element = *Pivot_element;
            *Pivot_element = Hold_it_here;
         }
         if (array[i] > *Pivot_element)
         {
            Hold_it_here = array[i];
            array[i] = *Pivot_element;
            *Pivot_element = Hold_it_here;
         }
         // Now use Hoare's partitioning algorithm
         j = r;
         for (;;)
         {
            do
            {
               ++i;
            } while (array[i] < *Pivot_element);
            do
            {
               --j;
            } while (array[j] > *Pivot_element);
            Hold_it_here = array[j];
            if (j <= i) // We've found our pivot element's location
               break;
            array[j] = array[i];
            array[i] = Hold_it_here;
         }
         array[j] = *Pivot_element;
         *Pivot_element = Hold_it_here;
         ascending(array,l,j-1);
         ascending(array,j+1,r);
      }
   }
}
template void descending(T array[], int l, int r)
{
   int i, j, const shorty = 8;
   T Hold_it_here;
   if (r > l)
   {
      // If the subfile is short use insertion sort
      if (r - l <= shorty)
      {
         for (i = l + 1; i <= r; ++i)
         {
            Hold_it_here = array[i];
            for (j = i; j > l && array[j-1] < Hold_it_here; --j)
               array[j] = array[j-1];
            array[j] = Hold_it_here;
         }
      }
      else
      {
         T * Pivot_element = &array[l], * Rightmost_element = &array[r];
         // Mid-point of current sub-file
         i = (l + r)/2;
         // Exchange the middle one and the leftmost
         Hold_it_here = *Pivot_element;
         *Pivot_element = array[i];
         array[i] = Hold_it_here;
         // Sort the leftmost, leftmost bar 1 and rightmost
         // such that:  leftmost bar 1 >= leftmost >= rightmost
         i = l + 1; // leftmost bar 1
         if (array[i] < *Rightmost_element)
         {
            Hold_it_here = *Rightmost_element;
            *Rightmost_element = array[i];
            array[i] = Hold_it_here;
         }
         if (*Pivot_element < *Rightmost_element)
         {
            Hold_it_here = *Rightmost_element;
            *Rightmost_element = *Pivot_element;
            *Pivot_element = Hold_it_here;
         }
         if (array[i] < *Pivot_element)
         {
            Hold_it_here = array[i];
            array[i] = *Pivot_element;
            *Pivot_element = Hold_it_here;
         }
         // Now use Hoare's partitioning algorithm
         j = r;
         for (;;)
         {
            do
            {
               ++i;
            } while (array[i] > *Pivot_element);
            do
            {
               --j;
            } while (array[j] < *Pivot_element);
            Hold_it_here = array[j];
            if (j <= i) // We've found our pivot element's location
               break;
            array[j] = array[i];
            array[i] = Hold_it_here;
         }
         array[j] = *Pivot_element;
         *Pivot_element = Hold_it_here;
         descending(array,l,j-1);
         descending(array,j+1,r);
      }
   }
}
============================================================================
Coming up next week, I will post the non-recursive version of the algorithm.
The calling sequence will be slightly simpler. Specifically, it will be the
same as that of the other sorting algorithms (Shellsort, Insertion sort,
Selection sort, etc.) that I have posted in this echo.
After that, I will post a benchmark program, possibly a few, that will
attempt to show each algorithm in its best and worst lights.
Regards
Dave

___
 * MR/2 2.25 #353 * I'm so broke I'm thinking of starting my own 
vernment...
--- Maximus/2 3.01
---------------