Help with a bucket sort please.

[dm06040]

I filled an array with a random generator. and that part of my code works fine. I just can't get it sort by using a bucket sort. I have looked them up with search engines but they are only confusing me more. Could somebody please help me out with this.

[dm06040]

Here is the code I have written to fill my array. Now I just can't figure out how sort it with a bucket sort.

[c]
#include <cstdlib>
#include <ctime>
#include <iostream.h>


int main ()

{


const int MAXELS = 20;

srand(time(NULL));
int i, numbers[MAXELS],z;
for(i=0; i<MAXELS; i++)
{


numbers[i] = 1.0 + (double)rand()/(double)(RAND_MAX + 1) * 99.00;



if (numbers[i] == z)
cout << "This is a duplicate number " <<numbers[i]<< "\n";
else
{

cout <<"\nThe code is: " <<numbers[i]<<endl;

z++;

}

}

return 0;
}
[/c]

[VHockey86]

I'm not familar with bucket sort, but if you know the range of the numbers you are sorting..(which would be the case when you are randomly generating numbers like this), counting sort is an "n" algorithm and very easy to implement. Most other sorts are n*log(n) or worse.

[SpookyEddy]

What part has you stumped?

I have just hacked together a quick bucket sort method in Ruby and the process would appear to have three stages...

1. Setup your buckets.
2. Iterate over your data set and stick each value in the corresponding bucket.
3. Look in each bucket and see if you have anything in it.

My crufty code...

class Array
  def bucketsort
    buckets = Array.new((self.max + 1), 0)

    self.each { |i| buckets[i] += 1 }

    sorted = Array.new
    buckets.each_index { |index| buckets[index].times { sorted << index } }

    return sorted
  end
end

If I get time later I will try and rewrite it in C++, but I wouldn't hold your breath

Regards

ed