Hi All,
At long last we have reached the version of Quicksort that uses the most
up-to-date version of the algorithm. This incorporates an Insertion sort for
short subfiles, Singleton's median-of-three pivot selection and now
Sedgewick's removal of recursion.
To remove recursion we need to use an explicit stack, rather than the
implicit one in the recursive calls. In order to implement this in a
reusable manner, I have coded up 2 template classes: one for stacking a
single value per generation; and one for stacking 2 values per generation. I
plan to use these classes in implementing non-recursive versions of other
sorting algorithms too.
So, here is the stack class:
============================= recurstk.hpp =================================
#ifndef _INCL_RECURSION_STACK
#define _INCL_RECURSION_STACK
// 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.
// Class definition for a stack to remove recursion.
// Primarily intended for Quicksort.
// A template class for a stack where each generation has 1 element
template class STACK1
{
private:
   unsigned int sp; // Next generation pointer
   T * stack;       // Stack of subscripts or pointers
public:
   // Constructor takes a default stack size of 20 generations
   STACK1(size_t n = 20)
   { sp = 0U; stack = new T[n]; }
   // Destructor cleans up allocation
   ~STACK1()
   { delete [] stack; }
   virtual void inline push(T val)
   { stack[sp++] = val; }
   // Pop routine returns true when stack is empty; false otherwise.
   virtual bool inline pop(T & val)
   { if (sp == 0U) return true;
         val = stack[--sp]; return false; }
   // Routine to indicate if stack is empty
   virtual bool inline IsEmpty()
   { return sp == 0U; }
};
// A template class for a stack where each generation has 2 elements
template class STACK2
{
private:
   unsigned int sp; // Next generation pointer
   T * left;        // Stack of left subscripts or pointers
   T * right;       // Stack of right subscripts or pointers
public:
   // Constructor takes a default stack size of 20 generations
   STACK2(size_t n = 20)
   { sp = 0U; left = new T[n]; right = new T[n]; }
   // Destructor cleans up allocations
   ~STACK2()
   { delete [] right; delete [] left; }
   virtual void inline push(T l, T r)
   { left[sp] = l; right[sp] = r; ++sp; }
   // Pop routine returns true when stack is empty; false otherwise.
   virtual bool inline pop(T & l, T & r)
   { if (sp == 0U) return true;
         --sp; l = left[sp]; r = right[sp];
         return false; }
   // Routine to indicate if stack is empty
   virtual bool inline IsEmpty()
   { return sp == 0U; }
};
#endif
============================================================================
And here is the updated function template:
============================= quicksrt.hpp =================================
// Templates for non-recursive Quicksort for ascending & descending sort.
// This is Sedgewick's version of Quicksort, a major evolution from
// Hoare's original, recursive algorithm.
// It also includes the Quickersort algorithm's usage of Insertion sort
// for short subfiles, and Singleton's median-of-three pivot selection.
// 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.
// Just in case the main program didn't do this, include our stack class
// for recursion removal.
#include "recurstk.hpp"
template void ascending(T array[], int n)
{
   int i, j, l, r, const shorty = 8;
   STACK2 stack_area(32);
   T Hold_it_here;
   // Use array bounds as initial left and right extremities.
   l = 0;
   r = n - 1;
   for (;;)
   {
      // Only use Quicksort on longer subfiles
      if (r - l > shorty)
      {
         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;
         // Push appropriate the bounds pair onto the stack
         if (j - l > r - j)
         {
            stack_area.push(l,j-1);
            l = j + 1;
         }
         else
         {
            stack_area.push(j+1,r);
            r = j - 1;
         }
      }
      else
      {
         // If the subfile is short use Insertion sort
         if (r > l)
         {
            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;
            }
         }
         // See if we're finished
         if (stack_area.pop(l,r))
            break;
      }
   }
}
template void descending(T array[], int n)
{
   int i, j, l, r, const shorty = 8;
   STACK2 stack_area(32);
   T Hold_it_here;
   // Use array bounds as initial left and right extremities.
   l = 0;
   r = n - 1;
   for (;;)
   {
      // Only use Quicksort on longer subfiles
      if (r - l > shorty)
      {
         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;
         // Push appropriate the bounds pair onto the stack
         if (j - l > r - j)
         {
            stack_area.push(l,j-1);
            l = j + 1;
         }
         else
         {
            stack_area.push(j+1,r);
            r = j - 1;
         }
      }
      else
      {
         // If the subfile is short use Insertion sort
         if (r > l)
         {
            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;
            }
         }
         // See if we're finished
         if (stack_area.pop(l,r))
            break;
      }
   }
}
============================================================================
These functions, above, should perform internal sorting about as fast as can
be done in C++ on general data, provided you use suitable overloads for the
comparison operators, , where needed.
On the Intel platform, you might be able to winkle a little more speed out
of 16-bit compilers by using pointers in place of subscripts in the small
memory model. Mileage can vary a bit on this, though.
For nostalgia buffs, it is almost exactly 20 years (mid 1978) since I first
coded a non-recursive Quicksort. I coded it from a copy of Sedgewick's Ph.D.
thesis. The language I used was IBM mainframe assembler, which was to run on
an IBM 370/145 under OS/VS1. The input medium was punched cards.
Regards
Dave

___
 * MR/2 2.25 #353 * Dear IBM: Hate you, hate OS/2, took your money and ran. - 
Bill Gates
--- Maximus/2 3.01
---------------