///////    File: arbqsort.C    ///////
#include        <iostream.h>
#include "arbqsort.h"

static int partition(void *any, int l, int r,
                     CMP_FN cmp, SWAP_FN swap)
{ register int i=l, j=r;
   // choose middle element as pivot 
     swap(any,(i+j)/2, r);                   // pivot moved to r
     while (i < j)
     {  while (cmp(any, i, r) <= 0 && i < j) // use supplied cmp  
           i++; 
        while(j > i && cmp(any, j, r) >= 0)  // use supplied cmp  
           j--;
        if (i < j) swap(any,i++,j);          // use supplied swap 
     }
     if (i != r) swap(any,i,r);              // use supplied swap 
     return(i);
}

void quicksort(void *any, int l, int r, CMP_FN cmp, SWAP_FN swap)
{    if ( l >= r || l < 0 || r < 0 ) return;
  // call with supplied functions 
     int k = partition(any, l, r, cmp, swap);
  // recursive calls              
     quicksort(any, l, k-1, cmp, swap);
     quicksort(any, k+1, r, cmp, swap);  
}