CODEWITHSUNDEEP
c++arrayssortingbucket-sort
zsloan112
zsloan112

Reputation: 43

Bucket Sort Implementation

I have to implement a bucket sort so that it sorts an array with size = 100 with randomly generated numbers between 0 and 100. My buckets are as follows: 

Bucket0: (0<=x<10)
Bucket1: (10<=x<20)
.
.
.
Bucket9: (90<=x<100)

Now I understand the theory behind the bucket sort, where I insert the elements into each individual bucket, but what I don't get it how to actually create the buckets. Do I create an array say B with the buckets being arrays themselves? Or is the a more standard way of implementing a bucket sort with integers?

I just need a nudge in the right direction, thanks for any help!

Upvotes: 0

Views: 848

Answers (1)

Yinon
Yinon

Reputation: 955

Yes.
You have to declare another array (we can say b) with length 101. The length represents and range of our numbers.

Now you have to over the first array and for each cell, and when you find every number k (0 <= k <= 100) , you have to ++ the b[k]. Something like: b[a[i]]++;

Now we have array b which represents how many times each number k appeared in the first array. We can override the first array:

for(int i = 0; i <= RANGE; i++)
    for(int j = 0; j < b[i]; j++)
        a[p++] = i;

While on your case, RANGE is 100.

Complexity: O(n)

Notice that we can implement that with one variable instead of using an array, which is doing the same thing, but every time for a different number. Not saves much but saves a little Complexity of space.

Upvotes: 1

Related Questions