Adding to my own collection of generic data structures, today I added a
generic Randomized Quicksort algorithm, I need a good sorting routine
in the SAPE algorithm for sorting distances. I want to makesure that
it can sort any kind array (array of char's,int's,float's,double's and
also structures).
/*A generic Randomized Quicksort:
*The key idea of being generic comes
*from the fact that you take a memory
*block and size of each element and
*sort this memory chunk, so we always
*deal with address's.
*
*
*Sep 20,2007 vamsik@engr.uconn.edu
**/
#include
#include
#include
#include
#include
#include "RandQsort.h"
/*INPUT: swap_routine,compare_routine
* swap_routine: The algorithm gives the
* (void *)'s swap_routine of two things
* which need to be swapped.
*
* compare_routine: The algorithm gives the
* (void *)'s to the compare_routine its
*/
static char QSORT_RAND_SEED=0;
static void (*swap_routine)(void *,void *) = NULL;
static unsigned char (*compare_routine_l)(void *,void *) = NULL;
static unsigned char (*compare_routine_g)(void *,void *) = NULL;
static time_t t_rqsort;
unsigned int GetPivot(void){
if(!QSORT_RAND_SEED){
assert(((time_t)-1)!=time(&t_rqsort));
srand(t_rqsort);
fprintf(stdout,"Setting RAND_SEED to %d \n",t_rqsort);
QSORT_RAND_SEED=1;
}
return ((unsigned int)rand());
}
/*Avoid loosing the pivot during swaps*/
void UpdatePivot(void **pivot,void **i,void **j){
if(*i==*pivot){
*pivot = *j;
}else if(*j == *pivot){
*pivot = *i;
}
}
/*Take a memory address location and size
of the data items[Inplace partition]*/
static void PartitionWithPivot(void* start,void* end,
unsigned int dsize){
void *pivot=NULL;
void* i=start;
void* j=end;
unsigned int p_index = GetPivot();
if(start==end){
return;
}
p_index %= (((unsigned int)(end-start))/dsize);
pivot=(void *)((unsigned long)start+
(unsigned long)((p_index)*dsize));
while(i=start)){
j-=dsize;
}
/*Swap i,j*/
if(istart){
swap_routine(pivot,(void *)(i-dsize));
PartitionWithPivot(start,(void *)(i-(2*dsize)),
dsize);
}
if((i+dsize)<=end){
PartitionWithPivot(i,end,dsize);
}
}
/*Call PartitionWithPivot recursively*/
void RandQsort(void *start,void *end,unsigned int dsize,
void_void_fptr sroutine,bool_void_fptr croutine_l){
swap_routine = sroutine;
compare_routine_l = croutine_l;
assert(swap_routine && compare_routine_l);
PartitionWithPivot(start,end,dsize);
}
#ifdef UNIT_TEST_RQSORT
/*TEST1:Testing for chars*/
unsigned char CharCompare_L(void *a,void *b){
return ((*((char *)a))<=(*((char *)b)))?1:0;
}
unsigned char CharCompare_G(void *a,void *b){
return ((*((char *)a))>=(*((char *)b)))?1:0;
}
void CharSwap(void *a,void *b){
char temp=*((char *)a);
*((char *)a) = *((char *)b);
*((char *)b) = temp;
}
void TestCharSort(){
char *data = malloc(sizeof(char)*10);
char test_buffer[64];
unsigned int i,j,k;
time_t test_time;
for(i=0;i<10;i++){
data[9-i] = '0'+i;
}
/*Randomize the input data*/
time(&test_time);
srand(test_time);
for(i=0;i<100;i++){
j=(rand())%10;
k=(rand())%10;
test_buffer[63]=data[j];
data[j]=data[k];
data[k]=test_buffer[63];
}
/*Print the buffer*/
if(strncpy(test_buffer,data,10)!=test_buffer){
fprintf(stderr,"SYSTEM_ISSUE:Copy into buffer failed\n");
}else{
test_buffer[10]='\0';
fprintf(stdout,"%s\n",test_buffer);
}
RandQsort((void *)data,(void *)(data+9),1,
CharSwap,CharCompare_L);
for(i=0;i<10;i++){
if(data[i]-('0'+i)){
printf("Test Failed for Chars\n");
printf("Expecting %d but found %d\n",i,
((unsigned int)data[i]-'0'));
exit(1);
}
}
test_buffer[0]='\0';
if(strncpy(test_buffer,data,10)!=test_buffer){
fprintf(stderr,"FAILED_TEST: UNABLE TO COPY BUFFER\n");
fprintf(stderr,"MAY_BE_SOME_MEMORY_CORRUPTION_DURING_SORT\n");
exit(1);
}else{
fprintf(stdout,"%s\n",data);
}
printf("Test Passed For Chars....\n");
}
unsigned char FloatCompare(void *a,void *b){
int a_int = (int)((*(float *)a)*10000);
int b_int = (int)((*(float *)b)*10000);
return (a_int<=b_int)?1:0;
}
void FloatSwap(void *a,void *b){
float temp;
temp = *((float *)a);
*((float *)a) = *((float *)b);
*((float *)b) = temp;
}
#include
void TestFloatSort(){
float *data = malloc(sizeof(float)*10);
float temp;
unsigned int i,j,k;
time_t test_time;
for(i=0;i<10;i++){
data[9-i] = (float)sin(i);
}
/*Randomize the input data*/
time(&test_time);
srand(test_time);
for(i=0;i<100;i++){
j=(rand())%10;
k=(rand())%10;
temp=data[j];
data[j]=data[k];
data[k]=temp;
}
/*Print the buffer*/
for(i=0;i<10;i++){
printf("%f ",data[i]);
}
printf("\n");
printf("The # of elements %d\n",(&data[9]-&data[0])/4);
RandQsort((void *)&data[0],(void *)&(data[9]),4,
FloatSwap,FloatCompare);
for(i=1;i<10;i++){
if(!FloatCompare((void *)&data[i-1],(void *)&data[i])){
printf("Test FAILED comparing %f , %f\n",
data[i-1],data[i]);
exit(1);
}
}
for(i=0;i<10;i++){
printf("%f ",data[i]);
}
printf("\n");
printf("Test Passed For Floats....\n");
}
/*Test for floats*/
int main(){
TestCharSort();
TestFloatSort();
exit(0);
}
#endif
