home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 9 / FreshFishVol9-CD2.bin / bbs / gnu / libnix-0.8-src.lha / libnix-0.8 / sources / nix / stdlib / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-12-12  |  1.7 KB  |  55 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
  17. (void *base,size_t nmemb,size_t size,int (*compar)(const void *,const void *))
  18. { char *base2=(char *)base;
  19.   char tmp;
  20.   size_t i,a,b,c;
  21.   while(nmemb>1)
  22.   { a=0;
  23.     b=nmemb-1;
  24.     c=(a+b)/2; /* Middle element */
  25.     for(;;)
  26.     { while((*compar)(&base2[size*c],&base2[size*a])>0) 
  27.         a++; /* Look for one >= middle */
  28.       while((*compar)(&base2[size*c],&base2[size*b])<0) 
  29.         b--; /* Look for one <= middle */
  30.       if(a>=b)
  31.         break; /* We found no pair */
  32.       for(i=0;i<size;i++) /* swap them */
  33.       { tmp=base2[size*a+i];
  34.         base2[size*a+i]=base2[size*b+i];
  35.         base2[size*b+i]=tmp; }
  36.       if(c==a) /* Keep track of middle element */
  37.         c=b;
  38.       else if(c==b)
  39.         c=a;
  40.       a++; /* These two are already sorted */
  41.       b--;
  42.     } /* a points to first element of right intervall now (b to last of left) */
  43.     b++;
  44.     if(b<nmemb-b) /* do recursion on smaller intervall and iteration on larger one */
  45.     { qsort(base2,b,size,compar);
  46.       base2=&base2[size*b];
  47.       nmemb=nmemb-b;
  48.     }
  49.     else
  50.     { qsort(&base2[size*b],nmemb-b,size,compar);
  51.       nmemb=b; }
  52.   }
  53.   return;
  54. }
  55.