home *** CD-ROM | disk | FTP | other *** search
/ EuroCD 3 / EuroCD 3.iso / Programming / vbcc / machines / amigappc / libsrc / stdlib / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-24  |  1.7 KB  |  54 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. /* sample compar function: int cmp(void *a,void *b){ return *(int *)a-*(int *)b; } */
  5.  
  6. /* This qsort function does a little trick:
  7.  * To reduce stackspace it iterates the larger interval instead of doing
  8.  * the recursion on both intervals.
  9.  * So stackspace is limited to 32*stack_for_1_iteration =
  10.  * 32*4*(4 arguments+1 returnaddress+11 stored registers) = 2048 Bytes,
  11.  * which is small enough for everybodys use.
  12.  * (And this is the worst case if you own 4GB and sort an array of chars.)
  13.  * Sparing the function calling overhead does improve performance, too.
  14.  */
  15.  
  16. void qsort (void *base,size_t nmemb,size_t size,int (*compar)(const void *,const void *))
  17. { char *base2=(char *)base;
  18.   char tmp;
  19.   size_t i,a,b,c;
  20.   while(nmemb>1)
  21.   { a=0;
  22.     b=nmemb-1;
  23.     c=(a+b)/2; /* Middle element */
  24.     for(;;)
  25.     { while((*compar)(&base2[size*c],&base2[size*a])>0)
  26.         a++; /* Look for one >= middle */
  27.       while((*compar)(&base2[size*c],&base2[size*b])<0)
  28.         b--; /* Look for one <= middle */
  29.       if(a>=b)
  30.         break; /* We found no pair */
  31.       for(i=0;i<size;i++) /* swap them */
  32.       { tmp=base2[size*a+i];
  33.         base2[size*a+i]=base2[size*b+i];
  34.         base2[size*b+i]=tmp; }
  35.       if(c==a) /* Keep track of middle element */
  36.         c=b;
  37.       else if(c==b)
  38.         c=a;
  39.       a++; /* These two are already sorted */
  40.       b--;
  41.     } /* a points to first element of right intervall now (b to last of left) */
  42.     b++;
  43.     if(b<nmemb-b) /* do recursion on smaller intervall and iteration on larger one */
  44.     { qsort(base2,b,size,compar);
  45.       base2=&base2[size*b];
  46.       nmemb=nmemb-b;
  47.     }
  48.     else
  49.     { qsort(&base2[size*b],nmemb-b,size,compar);
  50.       nmemb=b; }
  51.   }
  52.   return;
  53. }
  54.