Quick Sort Routine

[Rocky Moore]

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 at jacobs.cs.orst.edu