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.

I should have stated that when that code is run my program just crashes.

I believe the error is within the 2nd for loop but there may be several errors.

>I haven't been able to find much on the internet about it.
It's really nothing more than a bucket sort where each bucket holds a count for each number on the range:

#include <stdlib.h>

int pigeonhole_sort (
  int a[], int n,  /* Array and size of the array */
  int lo, int hi ) /* The range of values stored */
{
  int *buckets = malloc ( ( hi - lo ) * sizeof *buckets );
  int i, j, k;

  if ( buckets == NULL )
    return 0;

  /* Clear all counts */
  for ( i = 0; i < ( hi - lo ); i++ )
    buckets[i] = 0;

  /* Count the number of occurrences for each value */
  for ( i = 0; i < n; i++ )
    buckets[a[i] - lo] = buckets[a[i] - lo] + 1;

  k = 0;

  /* Copy non-empty buckets back to the array */
  for ( i = 0; i < ( hi - lo ); i++ ) {
    /* Repeat the value as necessary */
    for ( j = 0; j < buckets[i]; j++ )
      a[k++] = i + lo;
  }

  return 1;
}

>I will post my code below so you can point out any
>of the many errors you will find if you wish too.
Why are you using a hash table?

It's really nothing more than a bucket sort where each bucket holds a count for each number on the range

I did read about it being pretty much the same as the bucket sort. I will have a gander at that code in a bit and see if it helps me.

Why are you using a hash table?

I was told hash tables were required. Is this not true?

>I did read about it being pretty much the same as the bucket sort.
Yes and no. It's sort of half way between counting sort and bucket sort.

>I was told hash tables were required.
By whom? There is such a beast as a "hash sort", but I'm more inclined to believe that whoever told you hash tables are required doesn't really know what he's talking about.

>By whom? There is such a beast as a "hash sort", but I'm more inclined to believe that whoever told you hash tables are required doesn't really know what he's talking about.

Sorry, I was not actually told they were needed but I was told we need to use them to show we understand how to use them. He is what the specification I have says:

"The pigeon hole sort algorithm using a hash table where hash collisions are handled using linked lists (chained hashing). The hash table must be dynamically allocated based on the number of items to be sorted. If your code does not handle hash collisions you will be awarded limited marks."

I think you need to get more information. Either the specification is misleading about where you need to use a hash table, or the person who wrote it has a different idea of what a pigeonhole sort is.

I think you need to get more information. Either the specification is misleading about where you need to use a hash table, or the person who wrote it has a different idea of what a pigeonhole sort is.

I tried talking to him today but he didn't seem to want to offer much help. Thank you for trying to help though, it is much appreciated.

This article has been dead for over six months. Start a new discussion instead.