home *** CD-ROM | disk | FTP | other *** search
/ Informática Multimedia: Special Games / INFESPGAMES.mdf / os2 / ribble / support / cqsort.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-09  |  10.9 KB  |  479 lines
  1. // -------------------------------
  2. //  $Source: D:\logical\store\classes/RCS/CQSORT.H,v $
  3. //  $Revision: 1.13 $
  4. //  $Date: 1994/04/26 03:49:17 $
  5. //  $Author: jason $
  6. //  Language:       C++
  7. //  Licence:        Public Domain
  8. //  Purpose:        Sorting templates for arrays and CVectors
  9. // -------------------------------
  10.  
  11. #ifndef _CQSort_h
  12. #define _CQSort_h
  13.  
  14. #include <CSupport.h>
  15. #include <stdlib.h>
  16.  
  17. const long qsQuickSortThresh       = 4;
  18. const long qsQuickSortMedianThresh = 6;
  19.  
  20. // The following functions sort an array of
  21. // objects.
  22.  
  23. template <class T>
  24. void qsQuick_Sort(T huge* bot, ULONG nmemb);
  25.  
  26. template <class T>
  27. void qsInsertion_Sort(T huge* bot, ULONG nmemb);
  28.  
  29. template <class T>
  30. void
  31. QuickSort(T* bot, ULONG nmemb)
  32. {
  33.   if (nmemb <= 1)
  34.     return;
  35.  
  36.   if (nmemb >= qsQuickSortThresh)
  37.     qsQuick_Sort((T huge*)bot, nmemb);
  38.   else
  39.     qsInsertion_Sort((T huge*)bot, nmemb);
  40. }
  41.  
  42. template <class T>
  43. void
  44. qsQuickSwap(T huge* a, T huge* b)
  45. {
  46.   T tmp = *(T*)a;
  47.   *a = *b;
  48.   *b = tmp;
  49. }
  50.  
  51. template <class T>
  52. void
  53. qsDoSort(T huge*& bot, ULONG n, T huge*& t1)
  54. {
  55.   if (n > 1)
  56.     if (n == 2) 
  57.       {
  58.         t1 = bot + 1;
  59.         if (*(T*)t1 < *(T*)bot)
  60.           qsQuickSwap(t1, bot);
  61.       } 
  62.     else
  63.       qsInsertion_Sort(bot, (ULONG)n);
  64. }
  65.  
  66. template <class T>
  67. void
  68. qsQuick_Sort(T huge* bot, ULONG nmemb)
  69. {
  70.   T huge* top, huge* mid, huge* t1, huge* t2;
  71.   long n1, n2;
  72.   T huge* bsv;
  73.   
  74.   /* bot and nmemb must already be set. */
  75.  partition:
  76.   
  77.   /* find mid and top elements */
  78.   mid = bot + (nmemb >> 1);
  79.   top = bot + (nmemb - 1);
  80.   
  81.   /*
  82.    * Find the median of the first, last and middle element (see Knuth,
  83.    * Vol. 3, page 123, Eq. 28).  This test order gets the equalities
  84.    * right.
  85.    */
  86.   if (nmemb >= qsQuickSortMedianThresh) 
  87.     {
  88.       n1 = (*(T*)bot < *(T*)mid) ? -1 : (*(T*)bot == *(T*)mid) ? 0 : 1;
  89.       n2 = (*(T*)mid < *(T*)top) ? -1 : (*(T*)mid == *(T*)top) ? 0 : 1;
  90.       if (n1 < 0 && n2 > 0)
  91.         t1 = (*(T*)bot < *(T*)top) ? top : bot;
  92.       else if (n1 > 0 && n2 < 0)
  93.         t1 = (*(T*)bot > *(T*)top) ? top : bot;
  94.       else
  95.         t1 = mid;
  96.       
  97.       /* if mid element not selected, swap selection there */
  98.       if (t1 != mid) 
  99.         {
  100.           qsQuickSwap(t1, mid);
  101.           mid--;
  102.         }
  103.     }
  104.   
  105.   /* Standard quicksort, Knuth, Vol. 3, page 116, Algorithm Q. */
  106.   
  107.   long& didswap = n1;
  108.   T huge*& newbot = t1;
  109.   T huge*& replace = t2;          
  110.  
  111.   didswap = 0;
  112.   for (bsv = bot;;) 
  113.     {
  114.       for (; bot < mid && (*(T*)bot <= *(T*)mid); bot++);
  115.       while (top > mid)
  116.         {
  117.           if (*(T*)mid <= *(T*)top)
  118.             {
  119.               top--;
  120.               continue;
  121.             }
  122.           newbot = bot + 1;     /* value of bot after swap */
  123.           if (bot == mid)               /* top <-> mid, mid == top */
  124.             replace = mid = top;
  125.           else 
  126.             {                   /* bot <-> top */
  127.               replace = top;
  128.               top--;
  129.             }
  130.           goto swap;
  131.         }
  132.       if (bot == mid)
  133.         break;
  134.       
  135.       /* bot <-> mid, mid == bot */
  136.       replace = mid;
  137.       newbot = mid = bot;               /* value of bot after swap */
  138.       top--;
  139.       
  140.     swap:
  141.       qsQuickSwap(bot, replace);
  142.       bot = newbot;
  143.       didswap = 1;
  144.     }
  145.   
  146.   /*
  147.    * Quicksort behaves badly in the presence of data which is already
  148.    * sorted (see Knuth, Vol. 3, page 119) going from O N lg N to O N^2.
  149.    * To avoid this worst case behavior, if a re-partitioning occurs
  150.    * without swapping any elements, it is not further partitioned and
  151.    * is insert sorted.  This wins big with almost sorted data sets and
  152.    * only loses if the data set is very strangely partitioned.  A fix
  153.    * for those data sets would be to return prematurely if the insertion
  154.    * sort routine is forced to make an excessive number of swaps, and
  155.    * continue the partitioning.
  156.    */
  157.   if (!didswap)
  158.     {
  159.       qsInsertion_Sort(bsv, nmemb);
  160.       return;
  161.     }
  162.   
  163.   /*
  164.    * Re-partition or sort as necessary.  Note that the mid element
  165.    * itself is correctly positioned and can be ignored.
  166.    */
  167.   
  168.   long& nlower = n1;
  169.   long& nupper = n2;          
  170.   
  171.   bot = bsv;
  172.   nlower = (long)(mid - bot);    /* size of lower partition */
  173.   mid++;
  174.   nupper = nmemb - nlower - 1;  /* size of upper partition */
  175.   
  176.   /*
  177.    * If must call recursively, do it on the smaller partition; this
  178.    * bounds the stack to lg N entries.
  179.    */
  180.   if (nlower > nupper) 
  181.     {
  182.       if (nupper >= qsQuickSortThresh)
  183.         qsQuick_Sort(mid, (ULONG)nupper);
  184.       else 
  185.         {
  186.           qsDoSort(mid, (ULONG)nupper, t1);
  187.           if (nlower < qsQuickSortThresh) 
  188.             {
  189.               qsDoSort(bot, (ULONG)nlower, t1);
  190.               return;
  191.             }
  192.         }
  193.       nmemb = nlower;
  194.     } 
  195.   else 
  196.     {
  197.       if (nlower >= qsQuickSortThresh)
  198.         qsQuick_Sort(bot, (ULONG)nlower);
  199.       else 
  200.         {
  201.           qsDoSort(bot, (ULONG)nlower, t1);
  202.           if (nupper < qsQuickSortThresh) 
  203.             {
  204.               qsDoSort(mid, (ULONG)nupper, t1);
  205.               return;
  206.             }
  207.         }
  208.       bot = mid;
  209.       nmemb = nupper;
  210.     }
  211.   goto partition;
  212.   /* NOTREACHED */
  213. }
  214.  
  215.  
  216. template <class T>
  217. void
  218. qsInsertion_Sort(T huge* bot, ULONG nmemb)
  219. {
  220.   for (ULONG a = 0; a < nmemb; a++)
  221.     {
  222.       T& aElem = bot[a];
  223.       for (ULONG b = a + 1; b < nmemb; b++)
  224.         {
  225.           T& bElem = bot[b];
  226.           if (bElem < aElem)
  227.             {
  228.               T temp = aElem;
  229.               aElem = bElem;
  230.               bElem = temp;
  231.             }
  232.         }
  233.     }
  234. }
  235.  
  236.  
  237.  
  238.  
  239.  
  240.  
  241. //
  242. //
  243. //
  244. // The following functions sort an array of
  245. // pointers to objects.
  246. //
  247. //
  248. //
  249.  
  250. template <class T>
  251. void qsQuick_SortP(T huge*huge* bot, ULONG nmemb);
  252.  
  253. template <class T>
  254. void qsInsertion_SortP(T huge*huge* bot, ULONG nmemb);
  255.  
  256. template <class T>
  257. void
  258. QuickSortP(T** bot, ULONG nmemb)
  259. {
  260.   if (nmemb <= 1)
  261.     return;
  262.  
  263.   if (nmemb >= qsQuickSortThresh)
  264.     qsQuick_SortP((T huge*huge*)bot, nmemb);
  265.   else
  266.     qsInsertion_SortP((T huge*huge*)bot, nmemb);
  267. }
  268.  
  269. template <class T>
  270. void
  271. qsDoSortP(T huge*huge*& bot, ULONG n, T huge*huge*& t1)
  272. {
  273.   if (n > 1)
  274.     if (n == 2)
  275.       {
  276.         t1 = bot + 1;
  277.         if (**t1 < **bot)
  278.           qsQuickSwap(t1, bot);
  279.       }
  280.     else
  281.       qsInsertion_SortP(bot, (ULONG)n);
  282. }
  283.  
  284. template <class T>
  285. void
  286. qsQuick_SortP(T huge*huge* bot, ULONG nmemb)
  287. {
  288.   T huge*huge*top, huge*huge*mid, huge*huge*t1, huge*huge*t2;
  289.   long n1, n2;
  290.   T huge*huge*bsv;
  291.  
  292.   /* bot and nmemb must already be set. */
  293.  partition:
  294.  
  295.   /* find mid and top elements */
  296.   mid = bot + (nmemb >> 1);
  297.   top = bot + (nmemb - 1);
  298.  
  299.   /*
  300.    * Find the median of the first, last and middle element (see Knuth,
  301.    * Vol. 3, page 123, Eq. 28).  This test order gets the equalities
  302.    * right.
  303.    */
  304.   if (nmemb >= qsQuickSortMedianThresh)
  305.     {
  306.       if (**bot < **mid && **mid > **top)
  307.         t1 = **bot < **top ? top : bot;
  308.       else if (**bot > **mid && **mid < **top)
  309.         t1 = (**bot > **top) ? top : bot;
  310.       else
  311.         t1 = mid;
  312.  
  313.       /* if mid element not selected, swap selection there */
  314.       if (t1 != mid)
  315.         {
  316.           qsQuickSwap(t1, mid);
  317.           mid--;
  318.         }
  319.     }
  320.  
  321.   /* Standard quicksort, Knuth, Vol. 3, page 116, Algorithm Q. */
  322.  
  323.   long& didswap = n1;
  324.   T huge*huge*& newbot = t1;
  325.   T huge*huge*& replace = t2;
  326.  
  327.   didswap = 0;
  328.   for (bsv = bot;;)
  329.     {
  330.       for (; bot < mid && (**bot <= **mid); bot++);
  331.       while (top > mid)
  332.         {
  333.           if (**mid <= **top)
  334.             {
  335.               top--;
  336.               continue;
  337.             }
  338.           newbot = bot + 1;     /* value of bot after swap */
  339.           if (bot == mid)               /* top <-> mid, mid == top */
  340.             replace = mid = top;
  341.           else
  342.             {                   /* bot <-> top */
  343.               replace = top;
  344.               top--;
  345.             }
  346.           goto swap;
  347.         }
  348.       if (bot == mid)
  349.         break;
  350.  
  351.       /* bot <-> mid, mid == bot */
  352.       replace = mid;
  353.       newbot = mid = bot;               /* value of bot after swap */
  354.       top--;
  355.  
  356.     swap:
  357.       qsQuickSwap(bot, replace);
  358.       bot = newbot;
  359.       didswap = 1;
  360.     }
  361.  
  362.   /*
  363.    * Quicksort behaves badly in the presence of data which is already
  364.    * sorted (see Knuth, Vol. 3, page 119) going from O N lg N to O N^2.
  365.    * To avoid this worst case behavior, if a re-partitioning occurs
  366.    * without swapping any elements, it is not further partitioned and
  367.    * is insert sorted.  This wins big with almost sorted data sets and
  368.    * only loses if the data set is very strangely partitioned.  A fix
  369.    * for those data sets would be to return prematurely if the insertion
  370.    * sort routine is forced to make an excessive number of swaps, and
  371.    * continue the partitioning.
  372.    */
  373.  
  374.   if (!didswap)
  375.     {
  376.       if (nmemb < 500)
  377.         qsInsertion_SortP(bsv, nmemb);
  378.     }
  379.  
  380.   /*
  381.    * Re-partition or sort as necessary.  Note that the mid element
  382.    * itself is correctly positioned and can be ignored.
  383.    */
  384.  
  385.   long& nlower = n1;
  386.   long& nupper = n2;
  387.  
  388.   bot = bsv;
  389.   nlower = (long)(mid - bot);    /* size of lower partition */
  390.   mid++;
  391.   nupper = nmemb - nlower - 1;  /* size of upper partition */
  392.  
  393.   /*
  394.    * If must call recursively, do it on the smaller partition; this
  395.    * bounds the stack to lg N entries.
  396.    */
  397.   if (nlower > nupper)
  398.     {
  399.       if (nupper >= qsQuickSortThresh)
  400.         qsQuick_SortP(mid, (ULONG)nupper);
  401.       else
  402.         {
  403.           qsDoSortP(mid, (ULONG)nupper, t1);
  404.           if (nlower < qsQuickSortThresh)
  405.             {
  406.               qsDoSortP(bot, (ULONG)nlower, t1);
  407.               return;
  408.             }
  409.         }
  410.       nmemb = nlower;
  411.     }
  412.   else
  413.     {
  414.       if (nlower >= qsQuickSortThresh)
  415.         qsQuick_SortP(bot, (ULONG)nlower);
  416.       else
  417.         {
  418.           qsDoSortP(bot, (ULONG)nlower, t1);
  419.           if (nupper < qsQuickSortThresh) {
  420.             qsDoSortP(mid, (ULONG)nupper, t1);
  421.             return;
  422.           }
  423.         }
  424.       bot = mid;
  425.       nmemb = nupper;
  426.     }
  427.   goto partition;
  428.   /* NOTREACHED */
  429. }
  430.  
  431. // This isn't an Insertion sort!
  432. // Now a nice simple, easily debuggable Blubble Sort
  433.  
  434. template <class T>
  435. void
  436. qsInsertion_SortP(T huge*huge* bot, ULONG nmemb)
  437. {
  438.   ULONG i;
  439.   ULONG j;
  440.   T huge* v;
  441.  
  442.   for (i=1; i<nmemb; i++)
  443.     {
  444.       v = bot[i];
  445.       j = i;
  446.       while (j && *bot[j-1] > *v)
  447.         {
  448.           bot[j] = bot[j-1];
  449.           j--;
  450.         }
  451.       bot[j] = v;
  452.     }
  453.  
  454.  
  455. /*
  456.   for (ULONG a = 0; a < nmemb; a++)
  457.     {
  458.       T huge* aElem = bot[a];
  459.       for (ULONG b = a + 1; b < nmemb; b++)
  460.         {
  461.           T huge* bElem = bot[b];
  462.           if (*bElem < *aElem)
  463.             {
  464.               bot[b] = aElem;
  465.               aElem = bElem;
  466.             }
  467.         }
  468.       bot[a] = aElem;
  469.     }
  470. */
  471. }
  472.  
  473.  
  474.  
  475.  
  476.  
  477. #endif
  478.  
  479.