Thread: Bucket Sort or Myth

  1. #1
    Registered User
    Join Date
    Sep 2010
    Posts
    90

    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. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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;
    	}
    }
    Last edited by Elysia; 03-15-2011 at 02:33 PM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    Last edited by anon; 03-15-2011 at 02:10 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by Elysia View Post
    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. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Last edited by Elysia; 03-15-2011 at 02:34 PM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Registered User
    Join Date
    Sep 2010
    Posts
    90
    Elysia, what an explanation. You ARE a genius.

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

  7. #7
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by Elysia View Post
    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. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    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. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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?
    Last edited by anon; 03-15-2011 at 04:19 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #12
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by whiteflags View Post
    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. #13
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    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. #14
    Registered User
    Join Date
    Sep 2010
    Posts
    90
    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. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  2. Floating Exception (Core Dumped)
    By DarrenY in forum C Programming
    Replies: 9
    Last Post: 05-14-2007, 10:01 AM
  3. Clearing Buffer
    By AndyBomstad in forum C++ Programming
    Replies: 11
    Last Post: 04-30-2005, 01:04 AM
  4. Bucket Sort Problems... Please Help!
    By 67stangman in forum C++ Programming
    Replies: 1
    Last Post: 04-17-2002, 10:13 PM
  5. Bucket sort & list of lists ???
    By EasternStar in forum C Programming
    Replies: 1
    Last Post: 11-20-2001, 12:48 AM