moorer@jacobs.cs.orst.edu (Rocky Moore) (11/20/89)
I had noticed that someone wanted a binary sort routine which would allow you to do more than just more pointers. I wrote this little dab of code a while back when I needed a sort routine that I could use on a random disk file or on an array of structures in memory. --------- CUT HERE ------- /* QKSORT.C Started: May 15, 1987 6:19 AM * Finished: May 15, 1987 7:04 AM * * Quick Sort Routine. Uses int (*elcmp)() & void (*elswap)() to compare and * swap elements in the array. * * * Created By: Rocky Moore */ #include <stdio.h> /* -- Example Element Compare Routine int elcmp(e1,e2) int e1,e2; { return(strcmp(ary[e1],ary[e2])); } -- Example Element Swap Routine void elswap(e1,e2) int e1,e2; { void *tmp; tmp=ary[e1]; ary[e1]=ary[e2]; ary[e2]=tmp; } */ static int (*elcmp)(int,int); static void (*elswap)(int,int); static void sort_lst(startel,endel) int startel,endel; { int i, base, /* Base Element Pointer */ end, /* End Element Pointer */ ntarget; /* Target Element Number */ while(startel<endel) /* Until End Of List */ { base=startel; /* Set Base & End Pointers */ end=endel; ntarget=end; /* Set Target Pointers */ do { /* Find Nearest Low Match */ while(elcmp(base,ntarget)<0) { base++; if(base>=end) break; } end--; /* Find Nearest High Match */ if(base<end) while(elcmp(end,ntarget)>0) { end--; if(base>=end) break; } if(base>=end) break; /* Run Out Of List? */ elswap(base,end); /* Swap Base & End */ } while(1); /* Until End Of List */ elswap(base,ntarget); /* Swap Base & Target */ end=(startel+endel)/2; /* Calculate Which Half */ if(base>=end) { sort_lst(startel,base-1); /* Sort Upper Part Of List */ startel=base+1; } else { sort_lst(base+1,endel); /* Sort Lower Part Of List */ endel=base-1; } } /* All Done - Drop Thru */ } void qksort(start,end,fncmp,fnswp) int start,end; int (*fncmp)(); void (*fnswp)(); { elcmp=fncmp; elswap=fnswp; sort_lst(start,end); } --------- END HERE -------- This is a little primitive and could be optimized a little but should work fine with Turbo C 2.0 Hope it helps someone.. -Rocky Moore moorer@jacobs.cs.orst.edu