home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1994 #1 / monster.zip / monster / PROG_C / SNIP9404.ZIP / HUGESORT.C < prev    next >
C/C++ Source or Header  |  1994-04-03  |  3KB  |  106 lines
  1. /*
  2. **  hugesort.c -- huge qsort() -- public domain by Raymond Gardner 6/92
  3. **  tested with Borland C++ 3.0 (C mode)
  4. */
  5.  
  6. static void swap(char huge *a, char huge *b, unsigned n)
  7. {
  8.       char tmp;
  9.  
  10.       do
  11.       {
  12.             tmp = *a; *a++ = *b; *b++ = tmp;
  13.       } while ( --n );
  14. }
  15. void hugesort(void huge *basep,
  16.               unsigned   nel,
  17.               unsigned   width,
  18.               int      (*comp)(void huge *, void huge *))
  19. {
  20.       char huge *i, huge *j;
  21.       unsigned int lnel, rnel;
  22.       char huge *base = (char huge *)basep;
  23.  
  24.       while (nel > 1)
  25.       {
  26.             swap(base, base + (long)width * (nel / 2), width);
  27.             for (i = base, j = base + (long)width * nel; ; )
  28.             {
  29.                   do
  30.                         j -= width;
  31.                   while ( (*comp)(j, base) > 0 );
  32.                   do
  33.                         i += width;
  34.                   while ( i < j && (*comp)(i, base) < 0 );
  35.                   if (i >= j)
  36.                         break;
  37.                   swap(i, j, width);
  38.             }
  39.             swap(j, base, width);
  40.             lnel = (unsigned)((long)(j - base) / width);
  41.             rnel = nel - lnel - 1;
  42.             j += width;
  43.             if (lnel < rnel)
  44.             {
  45.                   hugesort(base, lnel, width, comp);
  46.                   base = j;
  47.                   nel = rnel;
  48.             }
  49.             else
  50.             {
  51.                   hugesort(j, rnel, width, comp);
  52.                   nel = lnel;
  53.             }
  54.       }
  55. }
  56.  
  57. #ifdef TEST
  58.  
  59. #include <stdio.h>
  60. #include <stdlib.h>
  61. #include <assert.h>
  62. #include <alloc.h>
  63.  
  64. #define PADSIZE 300
  65.  
  66. typedef struct x {
  67.     int key;
  68.     char pad[PADSIZE];
  69.     } X;
  70.  
  71. int cmpv(void huge *a, void huge *b) /* (note void huge *) passed here */
  72. {
  73.       return ((X huge *)a)->key < ((X huge *)b)->key ? -1 :
  74.             ((X huge *)a)->key > ((X huge *)b)->key ? 1 : 0;
  75. }
  76.  
  77. int main(int argc, char **argv)
  78. {
  79.       X huge *v;
  80.       int n;
  81.       int i, j;
  82.  
  83.       n = 300;                            /* default element count */
  84.       if (argc > 1)
  85.             n = atoi(argv[1]);
  86.       printf("test with %d elements\n", n);
  87.       v = farmalloc(sizeof(X) * (long)n);
  88.       assert(v);                          /* be sure we got memory */
  89.       for (i = 0; i < n; ++i)             /* random init */
  90.       {
  91.             v[i].key = rand();
  92.             for (j = 0; j < PADSIZE; ++j)
  93.                   v[i].pad[j] = rand();
  94.       }
  95.       for (i = 0; i < n; ++i)             /* display before */
  96.             printf(" %d", v[i].key);
  97.       printf("\n");
  98.       hugesort(v, n, sizeof(X), cmpv);    /* sort it */
  99.       for ( i = 0; i < n; ++i )           /* display after */
  100.             printf(" %d", v[i].key);
  101.       printf("\n");
  102.       return 0;
  103. }
  104.  
  105. #endif
  106.