In a message dated 03-20-98, Mathieu Bouchard said to Jonathan de Boyne
Pollard about Sort Algorithm
Hi Mathieu,
MB>Still, i think the canonical implementation of qsort() is made using
MB>the QuickerSort algorithm.
I suspect you are right. I, for one, would be too ashamed to release a
standard library that used bubble sort.
MB>BTW, would someone point out to me the difference between the QuickSort
MB>and the QuickerSort ?
The usual Quickersort incorporates Hoare's suggestion of using insertion
sort for shorter subfiles within Quicksort. And here is the code.
===============================quicksrt.hpp=================================
// Templates for Hoare's algorithm for ascending & descending sort.
// Note that this is Hoare's original, recursive algorithm with an insertion
// sort for shorter 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, Split_value;
   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
      {
         Split_value = array[r];
         i = l - 1;
         j = r;
         do
         {
            do
            {
               ++i;
            } while (array[i] < Split_value);
            do
            {
               --j;
            } while (array[j] > Split_value);
            Hold_it_here = array[i];
            array[i] = array[j];
            array[j] = Hold_it_here;
         } while (j > i);
         array[j] = array[i];
         array[i] = array[r];
         array[r] = Hold_it_here;
         ascending(array,l,i-1);
         ascending(array,i+1,r);
      }
   }
}
template void descending(T array[], int l, int r)
{
   int i, j, const shorty = 8;
   T Hold_it_here, Split_value;
   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
      {
         Split_value = array[r];
         i = l - 1;
         j = r;
         do
         {
            do
            {
               ++i;
            } while (array[i] > Split_value);
            do
            {
               --j;
            } while (array[j] < Split_value);
            Hold_it_here = array[i];
            array[i] = array[j];
            array[j] = Hold_it_here;
         } while (j > i);
         array[j] = array[i];
         array[i] = array[r];
         array[r] = Hold_it_here;
         descending(array,l,i-1);
         descending(array,i+1,r);
      }
   }
}
============================================================================
Have you or any lurkers tried my earlier code yet? [Or Jonathan's?]
Regards
Dave

___
 * MR/2 2.25 #353 * What does Windows NT stands for?  Nervous Technicians?
--- Maximus/2 3.01
---------------