home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-385-Vol-1of3.iso / s / snip1292.zip / HUGESORT.C < prev    next >
C/C++ Source or Header  |  1992-07-03  |  3KB  |  94 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.    do {
  10.       tmp = *a; *a++ = *b; *b++ = tmp;
  11.    } while ( --n );
  12. }
  13. void hugesort(void huge *basep, unsigned nel, unsigned width, 
  14.                             int (*comp)(void huge *, void huge *))
  15. {
  16.     char huge *i, huge *j;
  17.     unsigned int lnel, rnel;
  18.     char huge *base = (char huge *)basep;
  19.  
  20.     while ( nel > 1 ) {
  21.         swap(base, base + (long)width * (nel / 2), width);
  22.         for ( i = base, j = base + (long)width * nel; ; ) {
  23.             do
  24.                 j -= width;
  25.             while ( (*comp)(j, base) > 0 );
  26.             do
  27.                 i += width;
  28.             while ( i < j && (*comp)(i, base) < 0 );
  29.             if ( i >= j )
  30.                 break;
  31.             swap(i, j, width);
  32.         }
  33.         swap(j, base, width);
  34.         lnel = (long)(j - base) / width;
  35.         rnel = nel - lnel - 1;
  36.         j += width;
  37.         if ( lnel < rnel ) {
  38.             hugesort(base, lnel, width, comp);
  39.             base = j;
  40.             nel = rnel;
  41.         } else {
  42.             hugesort(j, rnel, width, comp);
  43.             nel = lnel;
  44.         }
  45.     }
  46. }
  47. #ifdef TEST
  48. #include <stdio.h>
  49. #include <stdlib.h>
  50. #include <assert.h>
  51. #include <alloc.h>
  52.  
  53. #define PADSIZE 300
  54.  
  55. typedef struct x {
  56.     int key;
  57.     char pad[PADSIZE];
  58.     } X;
  59.  
  60. int cmpv(void huge *a, void huge *b) /* (note void huge *) passed here */
  61. {
  62.     return ((X huge *)a)->key < ((X huge *)b)->key ? -1 :
  63.         ((X huge *)a)->key > ((X huge *)b)->key ? 1 : 0;
  64. }
  65.  
  66. int main(int argc, char **argv)
  67. {
  68.     X huge *v;
  69.     int n;
  70.     int i, j;
  71.  
  72.     n = 300;                            /* default element count */
  73.     if ( argc > 1 )
  74.         n = atoi(argv[1]);
  75.     printf("test with %d elements\n", n);
  76.     v = farmalloc(sizeof(X) * (long)n);
  77.     assert(v);                          /* be sure we got memory */
  78.     for ( i = 0; i < n; ++i )           /* random init */
  79.     {
  80.         v[i].key = rand();
  81.         for ( j = 0; j < PADSIZE; ++j )
  82.             v[i].pad[j] = rand();
  83.     }
  84.     for ( i = 0; i < n; ++i )           /* display before */
  85.         printf(" %d", v[i].key);
  86.     printf("\n");
  87.     hugesort(v, n, sizeof(X), cmpv);    /* sort it */
  88.     for ( i = 0; i < n; ++i )           /* display after */
  89.         printf(" %d", v[i].key);
  90.     printf("\n");
  91.     return 0;
  92. }
  93. #endif
  94.