I have managed to concur bubble sort, quick sort and heap sort but I've got stuck on pigeonhole sort. I haven't been able to find much on the internet about it.
I have wrote some code for it but it doesn't seem to work. I was wondering if any of you nice people could point me in the direction of a tutorial or something, even just an example.
What I basically want is to to sort random numbers into order.
I will post my code below so you can point out any of the many errors you will find if you wish too.
Any help at all will be appreciated!
void pigeonsort( int max, int random[] , int pigeon[] )
{
typedef struct node
{
int data;
struct node* next;
}NODE;
NODE **hashtable, *temp, *p1, *p2;
int i;
int j;
int hashnum;
int hashed;
float tempdata;
int counter[2] = {0,0};
//Copy random array to new array
memcpy( pigeon, random, (sizeof(int)*max));
hashnum= (int)(max*1.5);
hashtable = (NODE**) malloc(sizeof(NODE*)*hashnum);
for(i = 0; i < hashnum; i++)
{
hashtable[i] = NULL;
}// End of for loop.
for (i = 0; i < max; i++)
{
hashed = (int)((long)pigeon[i]*(long)hashnum/1000);
if (hashtable[hashed]==NULL)
{
counter[0]++;
hashtable[hashed] = (NODE*) malloc(sizeof(NODE));
hashtable[hashed]->data = pigeon[i];
hashtable[hashed]->next=NULL;
} //End of if statement.
else
{
temp = (NODE*)malloc(sizeof(NODE));
p2 = hashtable[hashed];
p1 = p2;
counter[0]++;
if(pigeon[i]<= p2->data)
{
hashtable[hashed] = temp;
temp->data = pigeon[i];
temp->next = p1;
}//End of if statement.
else
{
while(pigeon[i] > p2->data )
{
counter[0]++;
p1 = p2;
p2 = p2->next;
if(p2 == NULL) break;
}// End While loop.
counter[1]++;
p1->next = temp;
temp->data = pigeon[i];
temp->next = p2;
} //End else statement.
} // End outer Else statement.
}//End For loop.
for (i = 0, j = 0; i < hashnum; i++)
{
if(hashtable[i] != NULL)
{
p1 = hashtable[i];
while(p1 != NULL)
{
pigeon[j] = p1->data;
p2 = p1;
p1 = p1->next;
j++;
free(p2);
} //End While loop.
}//End if statement.
}//End For loop.
//Print out unsorted & sorted data
printf(" Unsorted || Sorted\n");
printf("----------||----------\n");
for(i = 0; i < max; i++)
{
printf(" %4d || %4d \n", random[i], pigeon[i]);
}
printf("Press Any Key to Continue");
getch();
free(hashtable);
}//End PigeonHole Sort.