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