home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / CTECHAPP.ZIP / STRATEGY.ZIP / HSORT.CPP next >
C/C++ Source or Header  |  1990-02-12  |  1KB  |  85 lines
  1. //  Module:     HSort
  2. //  Version:    1.00
  3. //
  4. //  Language:   C++ 2.0
  5. //  Environ:    Any
  6. //
  7. //  Purpose:    A HeapSort for arrays
  8. //
  9. //  Written by: Scott Robert Ladd
  10.  
  11. #include "HSort.hpp"
  12.  
  13. extern "C"
  14.     {
  15.     #include "string.h"
  16.     }
  17.  
  18.  
  19. void HeapSortArray::Sift()
  20.     {
  21.     int i, j;
  22.  
  23.     i = l;
  24.     j = 2 * l;
  25.  
  26.     src = ItemPtr(i);
  27.     memcpy(temp,src,Size);
  28.  
  29.     while (j <= r)
  30.         {
  31.         if (j < r)
  32.             if (Compare(ItemPtr(j),ItemPtr(j + 1)))
  33.                 ++j;
  34.  
  35.         if (Compare(ItemPtr(j),temp))
  36.             goto done;
  37.  
  38.         src  = ItemPtr(j);
  39.         dest = ItemPtr(i);
  40.  
  41.         memcpy(dest,src,Size);
  42.  
  43.         i = j;
  44.         j = 2 * i;
  45.         }
  46.  
  47.     done:
  48.  
  49.     dest = ItemPtr(i);
  50.  
  51.     memcpy(dest,temp,Size);
  52.     }
  53.  
  54. void HeapSortArray::Sort(void * arrayPtr, int arrayLen, int itemSize,
  55.                          int (* CompareFunc)(void * item1, void * item2))
  56.     {
  57.     SortArray::Sort(arrayPtr, arrayLen, itemSize, CompareFunc);
  58.  
  59.     temp = new char [Size];
  60.  
  61.     l = (arrayLen / 2) + 1;
  62.     r = arrayLen;
  63.  
  64.     while (l > 1)
  65.         {
  66.         --l;
  67.         Sift();
  68.         }
  69.  
  70.     while (r > 1)
  71.         {
  72.         src  = ItemPtr(1);
  73.         dest = ItemPtr(r);
  74.  
  75.         memcpy(temp,src,Size);
  76.         memcpy(src,dest,Size);
  77.         memcpy(dest,temp,Size);
  78.  
  79.         --r;
  80.         Sift();
  81.         }
  82.  
  83.     delete temp;
  84.     }
  85.