Pigeonhole sort C++

so there must be compiler errors, why dont you start posting it and we take it from there ..

>>   int size = 10;   //size of array to sort
>>   int nums[size];     //an array of ints

the same here ..

here you can see how to do it:

http://www.cplusplus.com/doc/tutorial/dynamic.html

The implementations I worked off of were indeed dynamically allocated arrays. The g++ compiler on the server I have been working off of compiles it just fine, and runs fine, but erroneously (just barely). I transferred into Visual Studio 2008, now I get compiler errors. I will take a look at this tonight, on my way out.

I made all arrays dynamically allocated, it compiles fine/runs fine in both g++ and visual studio. I was fairly sure it wasn't the problem. I've attached the new code snippet to reflect the two changes.

#include <iostream>
#include <cstdlib> //for random number generation
 
using namespace std;
 
 
/*
   function: void sort(int [],int&,int&)
   description: pigeonhole sort
   pre: integers are unique
   post: array is sorted
   input: array of int, int (size), int&(max item), int&(min item)
   output: none
           updates int&'s
*/
void sort(int [],int,int&,int&);
 
int main()
{
   //variables
 
   int size = 10;   //size of array to sort
   int* nums = new int[size];     //an array of ints
 
//------------------------------------------------------------
 
nums[0] = 52;
cerr << 52 << endl;
nums[1] = 34;
cerr << 34 << endl;
nums[2] = 12;
cerr << 12 << endl;
nums[3] = 98;
cerr << 98 << endl;
nums[4] = 45;
cerr << 45 << endl;
nums[5] = 58;
cerr << 58 << endl;
nums[6] = 32;
cerr << 32 << endl;
nums[7] = 39;
cerr << 39 << endl;
nums[8] = 1;
cerr << 1 << endl;
nums[9] = 80;
cerr << 80 << endl;
 
//------------------------------------------------------------
 
 
   //populate the array, the most time consuming part of the program
 
   for(int i = 0; i < 0; i++) //for every location in array
   {
      int random = rand()/1000;   //generates a random int
      for(int j = 0; j < size; j++)
      {
         /*
            if the integer is already in the array
            get a new one and start over. pigeonhole
            sort requires unique int (unique key)
 
            the size of the random int is cut down by
            dividing by 1000, this keeps results at
            a maximum size of 9999999 as per this 
            compilers setting for RAND_MAX
            this is done to reduce memory usage (by 1000x)
         */
 
         if(nums[j] == random)
         {
            random = rand()/1000;
            j = 0;
         }
      }
 
      nums[i] = random; // this is a unique number, use it
 
cerr << nums[i] << endl;
 
   }
 
   cout << "Random numbers generated: " << size << endl;
   cout << "Sorting..." << endl;
 
   //variables
 
   int max;
   int min;   
 
   //pigeonhole sort
 
   sort(nums,size,max,min);
 
 
///*
for(int i = 0; i < size; i++)
{
   cerr << nums[i] << endl;
}
//*/
 
   cout << "Done!\nMax was: " << max << "\nMin was: " << min
        << endl;
 
//cerr << endl << RAND_MAX << endl;   
 
   return 0;
}
 
 
void sort(int nums[], int size, int& mainsMax, int& mainsMin)
{
   //min item, for indexing
   int min = nums[0];
   
   //max item, for indexing
   int max = nums[0];
 
   //find the max and min items
 
   for(int i = 0; i < size; i++)
   {
      if(nums[i] < min)
         min = nums[i];
      if(nums[i] > max)
         max = nums[i];
   }
 
 
   mainsMin = min;
   mainsMax = max;
 
   int neededHoles = max - min + 1;
 
   int* holes = new int[neededHoles];
   for(int i = 0; i < neededHoles; i++)
   {
      holes[i] = 0;
   }
 
   for(int i = 0; i < size; i++)
   {
      holes[nums[i] - min]++;
   }
 
 
   int i = 0;
 
   for(int count = 0; count < (max - min); count++)
   {
      while(holes[count]-- > 0)
      {
         nums[i++] = count + min;
      }
   }
 
}

Select allOpen in new window

The idea behind this sort, if it helps -

1. find the range of values
2. create an array big enough to where the indexes are the value of the int in the actual array
3. flip all ints in second to zero
4. iterate through the original array, for each value, increment the second arrays index corresponding
5. iterate through the new array and put the value of its INDEX into the original array when its value is true

so if you had 1,6,8,9
the second array with have indexes 0 - 8, the min is is an offset that just saves a bit of memory. When you encounter 1, the new array's 0 index is flipped from zero to one, signifying the index is a value in the first array.
6 would flip 5 on
8 would flip seven on
9 would flip 8 on
the pigeonhole array would contain the values  1,0,0,0,0,1,0,1,1

when you traverse back through the pigeonhole array, you store the index of a true value (the value can be repeated when dealing with ints, the above code shows this with the while loop) into the original array, they just so happen to be sorted now. the original array would contain 1,6,8,9. Optimally this is O(n) and at worst O(n + k) (n numbers to sort and k the number of pigeonholes in that second array). The downfall is memory usage, but this is a beautiful sort when applied properly to right problem.

This can be applied to any data type if a unique key is used, hence why avoid pushing how in this example, the ints don't actually need to be unique.

I just can't see the error for the life of me, maybe i need new contacts.

Hoorah, on the very last loop (for) of the sort() function, the condition comparison right side should have been (max - min + 1) not (max - min). I didn't think to look very hard here because it was how it was written from where I translated in C++, I have no doubt, getting that language out, and typing in their code character for character is an erroneous pigeonhole sort. Should have wrote the whole deal myself from the psuedo-algorithm (in other words, understandable) I just came up with above.

You get all the points for being the only one willing to help. Throw something in open discussion if you see anything.

>> The g++ compiler on the server I have been working off of compiles it just fine

really, what g++ version did you use?

>> Hoorah ..

great :)

>> You get all the points for being the only one willing to help

please only award the points if the answer helped you. dont want the points just for being the only one .. ;)
otherwise you can ask for deleting the question ..


ike

gcc-3.4.6 2007-07-19