diff options
Diffstat (limited to 'libc/src')
-rwxr-xr-x | libc/src/qsort.c | 51 |
1 files changed, 51 insertions, 0 deletions
diff --git a/libc/src/qsort.c b/libc/src/qsort.c new file mode 100755 index 0000000..eeb038b --- /dev/null +++ b/libc/src/qsort.c @@ -0,0 +1,51 @@ +#include <stdio.h> +#include <stdlib.h> + +/* sample compar function: int cmp(void *a,void *b){ return *(int *)a-*(int *)b; } */ + +/* This qsort function does a little trick: + * To reduce stackspace it iterates the larger interval instead of doing + * the recursion on both intervals. + * So stackspace is limited to 32*stack_for_1_iteration = + * 32*4*(4 arguments+1 returnaddress+11 stored registers) = 2048 Bytes, + * which is small enough for everybodys use. + * (And this is the worst case if you own 4GB and sort an array of chars.) + * Sparing the function calling overhead does improve performance, too. + */ + +void qsort +(void *base,size_t nmemb,size_t size,int (*compar)(const void *,const void *)) +{ char *base2=(char *)base; + size_t i,a,b,c; + while(nmemb>1) + { a=0; + b=nmemb-1; + c=(a+b)/2; /* Middle element */ + for(;;) + { while((*compar)(&base2[size*c],&base2[size*a])>0) + a++; /* Look for one >= middle */ + while((*compar)(&base2[size*c],&base2[size*b])<0) + b--; /* Look for one <= middle */ + if(a>=b) + break; /* We found no pair */ + for(i=0;i<size;i++) /* swap them */ + { char tmp=base2[size*a+i]; + base2[size*a+i]=base2[size*b+i]; + base2[size*b+i]=tmp; } + if(c==a) /* Keep track of middle element */ + c=b; + else if(c==b) + c=a; + a++; /* These two are already sorted */ + b--; + } /* a points to first element of right intervall now (b to last of left) */ + b++; + if(b<nmemb-b) /* do recursion on smaller intervall and iteration on larger one */ + { qsort(base2,b,size,compar); + base2=&base2[size*b]; + nmemb=nmemb-b; } + else + { qsort(&base2[size*b],nmemb-b,size,compar); + nmemb=b; } + } +} |