home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / Test Code Folder / Shared Test Code / myqsort.c next >
Encoding:
C/C++ Source or Header  |  1998-04-25  |  4.7 KB  |  196 lines  |  [TEXT/CWIE]
  1. /*----------------------------------------------------------------------------
  2.  
  3.     myqsort.c
  4.  
  5.     This reentrant and reusable module implements a fast quicksort algorithm.
  6.     
  7.     Original version by Haydn Huntley. Modified to support reentrancy and
  8.     error handling (e.g., user cancels) by John Norstad.
  9. ----------------------------------------------------------------------------*/
  10.  
  11. #include <stdlib.h>
  12. #include "myqsort.h"
  13.  
  14. typedef struct TSortInfo {
  15.     long size;
  16.     SortCmpFunction cmp;
  17. } TSortInfo;
  18.  
  19.  
  20.  
  21. /*----------------------------------------------------------------------------
  22.     MemSwap 
  23.     
  24.     Exchange two array elements.
  25.             
  26.     Entry:    p = pointer to first element.
  27.             q = pointer to second element.
  28.             size = size of elements.
  29. ----------------------------------------------------------------------------*/
  30.  
  31. static void MemSwap (register char *p, register char *q, 
  32.     register long size)
  33. {
  34.     register char tmp;
  35.     
  36.     while (size--) {
  37.         tmp = *p;
  38.         *p++ = *q;
  39.         *q++ = tmp;
  40.     }
  41. }
  42.  
  43.  
  44.  
  45. /*----------------------------------------------------------------------------
  46.     ChooseMedian
  47.     
  48.     Select the median of three array elements and swap it with a destination
  49.     element.
  50.     
  51.     Entry:    pDest = pointer to destination element.
  52.             pA, pB, pC = pointer to three elements.
  53.             sortInfo = pointer to sort info.
  54.             
  55.     Exit:    function result = error code.
  56. ----------------------------------------------------------------------------*/
  57.  
  58. static OSErr ChooseMedian (void *pDest, void *pA, void *pB, void *pC,
  59.     TSortInfo *sortInfo)
  60. {
  61.     register void *pMedian;
  62.     register SortCmpFunction cmp;
  63.     short result;
  64.     OSErr err;
  65.     
  66.     cmp = sortInfo->cmp;
  67.     err = (*cmp)(pA, pB, &result);
  68.     if (err != noErr) return err;
  69.     if (result > 0) {                        /* pA > pB, what is pC?            */
  70.         err = (*cmp)(pA, pC, &result);
  71.         if (err != noErr) return err;
  72.         if (result > 0) {                    /* pA > pB, pA > pC                */
  73.             err = (*cmp)(pB, pC, &result);
  74.             if (err != noErr) return err;
  75.             if (result > 0)
  76.                 pMedian = pB;                /* pA > pB > pC                    */
  77.             else
  78.                 pMedian = pC;                /* pA > pC > pB                    */
  79.         } else {
  80.             pMedian = pA;                    /* pC > pA > pB                    */
  81.         }
  82.     } else {                                /* pB > pA, what is pC?            */
  83.         err = (*cmp)(pA, pC, &result);
  84.         if (err != noErr) return err;
  85.         if (result > 0) {
  86.             pMedian = pA;                    /* pB > pA > pC                    */
  87.         } else {                            /* pB > pA, pC > pA                */
  88.             err = (*cmp)(pB, pC, &result);
  89.             if (err != noErr) return err;
  90.             if (result > 0)
  91.                 pMedian = pC;                /* pB > pC > pA                    */
  92.             else
  93.                 pMedian = pB;                /* pC > pB > pA                    */
  94.         }
  95.     }
  96.     if (pDest != pMedian) MemSwap(pDest, pMedian, sortInfo->size);
  97.     return noErr;
  98. }
  99.  
  100.  
  101.  
  102. /*----------------------------------------------------------------------------
  103.     DoFastQSort
  104.     
  105.     Entry:    first = pointer to first element 
  106.                 of array in range to be sorted.
  107.             last = pointer to element following last element
  108.                 of array in range to be sorted. 
  109.             sortInfo = pointer to sort info.
  110.     
  111.     Exit:    function result = error code.
  112. ----------------------------------------------------------------------------*/
  113.  
  114. static OSErr DoFastQSort (register char *first, char *last, TSortInfo *sortInfo)
  115. {
  116.     register SortCmpFunction cmp;
  117.     register char *i, *j;
  118.     register long n, size;
  119.     OSErr err;
  120.     short result;
  121.          
  122.     size = sortInfo->size;
  123.     cmp = sortInfo->cmp;
  124.     while ((n = (last - first) / size) > 1) {
  125.         if (n < 25) {
  126.             MemSwap(first + (rand() % n) * size, first, size);
  127.         } else {
  128.             err = ChooseMedian(first, first, first + (n / 2) * size, 
  129.                 first + (rand() % n) * size, sortInfo);
  130.             if (err != noErr) return err;
  131.         }
  132.         i = first;
  133.         j = last;
  134.         while (true) {
  135.             i += size;
  136.             while (i < last) {
  137.                 err = (*cmp)(i, first, &result);
  138.                 if (err != noErr) return err;
  139.                 if (result >= 0) break;
  140.                 i += size;
  141.             }
  142.             j -= size;
  143.             while (j > first) {
  144.                 err = (*cmp)(j, first, &result);
  145.                 if (err != noErr) return err;
  146.                 if (result <= 0) break;
  147.                 j -= size;
  148.             }
  149.             if (i >= j) break;
  150.             MemSwap(i, j, size);
  151.         }
  152.         if (j == first) {
  153.             first += size;
  154.             continue;
  155.         }
  156.         MemSwap(first, j, size);
  157.         if (j - first < last - (j + size)) {
  158.             err = DoFastQSort(first, j, sortInfo);
  159.             if (err != noErr) return err;
  160.             first = j + size;
  161.         } else {
  162.             err = DoFastQSort(j + size, last, sortInfo);
  163.             if (err != noErr) return err;
  164.             last = j;
  165.         }
  166.     }
  167.     return noErr;
  168. }
  169.  
  170.  
  171.  
  172. /*----------------------------------------------------------------------------
  173.     FastQSort
  174.     
  175.     Sort an array.
  176.     
  177.     Entry:    base = pointer to first array element.
  178.             n = number of array elements.
  179.             size = size of array elements.
  180.             cmp = pointer to array element comparison function.
  181.             
  182.     Exit:    function result = error code. 
  183. ----------------------------------------------------------------------------*/
  184.  
  185. OSErr FastQSort (void *base, long n, long size, SortCmpFunction cmp)
  186. {
  187.     TSortInfo sortInfo;
  188.     
  189.     srand(TickCount());
  190.     
  191.     sortInfo.cmp = cmp;
  192.     sortInfo.size = size;
  193.     
  194.     return DoFastQSort(base, (char*)base + n * size, &sortInfo);
  195. }
  196.