# Thread: Bucket Sort or Myth

1. ## Bucket Sort or Myth

Hello. I need help with the Bucket Sort. I searched through the C++ board, as well as my book and couldn't find anything useful to me. The code is below.
Thanks!
Bucket Sort

That was 03-07-2003 .... It's now 03-15-2011 and I did the same thing for over 5 days straight (24/7 for a few of those days) and I can assure that you are right EasternStar. To this day 2011, it is not in any textbook and there is no examples WHAT-SO-EVER on the INTERNET to be found other than VERY LITTLE conversation and a few worthless papers floating around (if that much), and that's why no one has responded to you in nearly 10 years.

After all the stuff I read on the INTERNET about BUCKET SORT that lead to JACK nothing. it kind of make you feel like a guinea pig or the system hope that you are the ONE super-brain to come up with the code. The almighty textbooks shows some kind of example code to teach you about insertion, selection, bubble sort and ALL others, but since C++ was invented they have the nerve ask you to solve a problem using BUCKET SORT that can't be found no where on plant earth unless you are some kind of mathematician or working for NASA. Unlike the medical field, C++ may teach you brain surgery, but give you as homework a scalpel to cut out somebody pie where the sun don't shine. The funny thing is, our communities will dare you to ask for help... like they really knew the answer, already. I nearly read them ALL!

Since this is the all EVIL homework for me this round, my only question is would it be to asking to much for a link that will show some kind of working Bucket Sort code that even a student like me can learn from. It don't have to be of rocket science caliber ... just something simple that really works and from there I'll see to it that man can live on Mars.

Thank you

2. Ah, I know my book had an example of a bucket sort, actually.
The idea is this:
Make several buckets. Each bucket can hold one type of item only. So every item you find of a type you place into that bucket.
Then you keep your buckets sorted so you know which bucket contains the biggest item and which the lowest.
After sorting all your data into your buckets, you do the reverse: you begin with the biggest (or lowest) bucket, you empty its contents into your new data set and gradually go from the biggest to lowest (or the other way around).

Well, that sounds awfully abstract. What does it mean? Let's take an example with integers.
In this case, we can let each bucket represent a number. So each bucket contains a number of the same number. Let's say we simplify this by putting the number of said items in the same bucket.
For example, say we have, in our data to sort, 1 3 5 5 7 2.
Create buckets 1, 3, 5, 7 and 2. Put into bucket 1, 1, into bucket 3, 1, into bucket 5, 2, into bucket 7, 1 and into bucket 2, 1 (the occurrences of each number in our data to sort).

Now, let's do this in reverse. Begin with the biggest bucket, empty it into the sorted data, then continue with the next, and so on.
So it might look like:

Take lowest bucket 1, empty into data stream:
1
Bucket 2:
1 2
Bucket 3:
1 2 3
Bucket 5:
1 2 3 5 5
Bucket 7:
1 2 3 5 5 7

And we're done.

An example of an implementation may be this:
Code:
```#include <vector>
#include <limits>

template<typename InputIt, typename OutputIt>
void Sort(InputIt InputBegin, InputIt InputEnd, OutputIt OutputStart)
{
typedef typename InputIt::value_type It_t;
std::vector<It_t> buckets(std::numerical_limits<InputIt>::max());
while (InputBegin++ != InputEnd)
buckets(*InputBegin)++;
for (auto it = buckets.begin(), end = buckets.end(); it != end; ++it)
{
for (It_t i = 0; i < *it; i++)
*OutputStart++ = *it;
}
}```

3. Have you checked out Wikipedia: bucket sort?

As to the code posted 10 years ago, well, there isn't even a question there. That person does not even indicate whether he is having trouble with the algorithm, or just the syntax of C++. These kinds of questions that just dump some broken code do not motivate people to reply.

The algorithm itself doesn't seem to be rocket science.

4. Originally Posted by Elysia
Code:
`std::numerical_limits<InputIt>::max()`
numerical_limits works for an iterator type, does it? And then you switch to shorts in the middle of the example. Hmm...

5. Heh. I originally wrote it with short, but then changed to iterator type, so I guess there may be some bugs.
It's just an example, though.

EDIT: I made some changes based on what information I could find about what typedefs the iterator exposes. Maybe it works better now. Maybe not.

6. Elysia, what an explanation. You ARE a genius.

... and you other guys never half-stepped either. Wow!

7. Originally Posted by Elysia
Heh. I originally wrote it with short, but then changed to iterator type, so I guess there may be some bugs.
It's just an example, though.

EDIT: I made some changes based on what information I could find about what typedefs the iterator exposes. Maybe it works better now. Maybe not.
Well as you're finding out, the trouble with a one-size-fits all bucket sort is that you have to know what to make buckets for. It's not necessarily anything discrete like a type integer versus type foo. I could use bucket sort to sort employees by position, or something. An associative array is more helpful in most real-world uses of this sort.

8. Bucket sort could be implemented in all kinds of ways, but this is the only sort I know of that work in O(N) time, provided there are not too many duplicates of data. It's pretty cool, and worth showing IMO.
Otherwise bucket sort will be overshadowed by other sorts suck as Quicksort, mergesort and heapsort.

9. Radix sort also works in O(N) time, as does counting sort -- which, I think, isf what you are trying to implement as an example of bucket sort is.

10. Have to admit, I didn't know of them. So many algorithms out there, yet you only learn a handful of them. Oh well.
Well, at least it is one possible implementation. And it is an example of how bucket sort works.
Since I haven't implemented any other version or given it any thought, I don't have any other examples to show.

11. It might indeed be better to implement it like the Wikipedia page shows.

Elysia, I think using numeric_limits<T>::max is highly problematic (value might be too large to allocate, not speaking about being practical). If the data is known to be in a limited range, you might perhaps use min_max_element to find the required size (for a counting sort). Perhaps it would also be possible to switch to real bucket sort, if the range of data is too large for a counting sort to be practical?

12. Originally Posted by whiteflags
Radix sort also works in O(N) time, as does counting sort -- which, I think, isf what you are trying to implement as an example of bucket sort is.
I just want to point out that O(N) is not an improvement over O(N log N) here. The lofty O(N) claimed by these unusual sorting algorithms relies on a fixed finite set of values to sort, which really means for large values of N you just have tons of duplicate values. It's impossible to sort N distinct values in O(N) time.

(Unless you use bogosort and destroy_universe() is available Bogosort - Wikipedia, the free encyclopedia)

13. The lofty O(N) claimed by these unusual sorting algorithms relies on a fixed finite set of values to sort
I want to point out that the only reason you would use those sorts (logically) is because this describes the situation.

14. So many algorithms out there, yet you only learn a handful of them. Oh well ...
.. Elysia, other than your wonderful breakdown of Bucket Sort, I forgot to Thank You for taking a stab at presenting a full basic implementation of some code which was related to "our" original question, but better.

Anyway, this should complete your sorting arsenal forever. Things may kick-in for me as well as others as we pay attention, as long as flames don't get thrown because of the subject. Also, I found the right keywords to use a few hours ago. It is "BucketSorter" or BucketSorter "Vector".

"C++ Bucket Sort" or "Bucket Sort" as keyword is useless. It only return mostly something NOT related to C++ coding or kibbles-and-bits of C++ code that will never work.

Doom Doom... I found this:
C++ Source Code
Basic Algorithms: Lecture #23
It's in here!

15. Well I must admit, I'm a tad disappointed if my own site didn't register as a source of bucket sort code on google.
A linked-list version of Bucket Sort in C++ is here.
When it comes to arrays instead of lists, I find that FlashSort which essentially distributes items throughout the array in "buckets", is a more efficient alternative.

Check out the rest of the sorting stuff which you can find by clicking the link in my signature. More sorting algorithms in one small site than you've ever seen, guaranteed!

Popular pages Recent additions