home *** CD-ROM | disk | FTP | other *** search
/ Black Box 4 / BlackBox.cdr / progc / cfuncs.arj / HUGESORT.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-08-15  |  2.4 KB  |  116 lines
  1. #include <alloc.h>
  2. #include <mem.h>
  3.  
  4. char *temp;
  5. size_t Width;
  6. int (*Fcmp) (const void huge *, const void huge *);
  7.  
  8. void exchange(char huge *elt1, char huge *elt2)
  9. {
  10.    int i;
  11.  
  12.    for(i=0; i<Width; ++i)
  13.       temp[i] = elt1[i];
  14.    for(i=0; i<Width; ++i)
  15.       elt1[i] = elt2[i];
  16.    for(i=0; i<Width; ++i)
  17.       elt2[i] = temp[i];
  18. }
  19.  
  20. size_t partition(char huge *base, size_t first, size_t last)
  21. {
  22.  
  23.    void huge *pivot;
  24.    size_t up, down;
  25.  
  26.    pivot = base+(long)first*Width;
  27.    up = first;
  28.    down = last;
  29.  
  30.    do
  31.    {
  32.       while (Fcmp(base+(long)up*Width, pivot) <= 0 && up < last)
  33.     ++up;
  34.  
  35.       while(Fcmp(base+(long)down*Width, pivot) > 0)
  36.     --down;
  37.  
  38.       if(up < down)
  39.       {
  40.      exchange(base+(long)up*Width, base+(long)down*Width);
  41.       }
  42.    } while( up < down);
  43.  
  44.    exchange(base+(long)first*Width, base+(long)down*Width);
  45.  
  46.    return(down);
  47. }
  48.  
  49. void QuickSort(void huge *base, size_t first, size_t last)
  50. {
  51.     size_t  PivIndex;
  52.  
  53.     if(first < last)
  54.     {
  55.        PivIndex = partition(base, first, last);
  56.        QuickSort(base, first, PivIndex-1);
  57.        QuickSort(base, PivIndex+1, last);
  58.     }
  59. }
  60.  
  61. /*--------------------------HugeQsort-------------------------*/
  62. /*DESCRIPTION: the QuickSort algorithm using huge pointers    */
  63. /*                                  */
  64. /* paramaters and returns are the same as the C qsort excpt   */
  65. /* all pointers are huge                      */
  66. /*------------------------------------------------------------*/
  67.  
  68. void HugeQsort(void huge *base, size_t nelem, size_t width, int (*fcmp)
  69.         (const void huge *, const void huge *))
  70. {
  71.     temp = malloc(width);
  72.     Width = width;
  73.     Fcmp = fcmp;
  74.  
  75.     QuickSort(base, 0, nelem-1);
  76.  
  77.     free(temp);
  78. }
  79.  
  80. void huge *HugeBsearch(const void *key, const void huge *base, size_t nelem,
  81.     size_t width, int (*fcmp)(const huge void*, const void*))
  82. {
  83.    int   cmp;
  84.    long last;    /* because last may be negative & int is too small */
  85.    size_t middle, first;
  86.  
  87.    first = 0;
  88.    last = nelem-1;
  89.  
  90.    do
  91.    {
  92.       middle = ((long)first+last)/2;
  93.       if((cmp = fcmp((char huge *)base+(long)middle*width, key)) > 0)
  94.     last = middle -1l;
  95.       else
  96.     first = middle +1;
  97.    }while(first <= last && cmp != 0);
  98.  
  99.    if(cmp==0)
  100.     return((char huge *)base+(long)middle*width);
  101.    else
  102.     return(NULL);
  103. }
  104.  
  105. /*
  106. int Fstrcmp(const char *str1, const char *str2)
  107. {
  108.     int i = -1;
  109.  
  110.     while(!(str1[++i]-str2[i]) && str1[i])
  111.     ;
  112.     return(str1[i] - str2[i]);
  113. } */
  114.  
  115.  
  116.