Like Tree2Likes

Bucket Sort or Myth

This is a discussion on Bucket Sort or Myth within the C++ Programming forums, part of the General Programming Boards category; O_o Okay, sharris, you have 53 posts; you should know better by now. How has someone not told you? Always ...

  1. #31
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,217
    O_o

    Okay, sharris, you have 53 posts; you should know better by now. How has someone not told you?

    Always copy and paste the code you are actually working with. That code wouldn't even compile so commenting on the idea implemented is pointless.

    Soma

  2. #32
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by anon View Post
    Again, this seems to be a counting sort.
    Yes that code is basically counting sort, and the previous pseudocode was actually describing radix sort!

    Perhaps part of the reason you're not heading for the right algorithm is that when only sorting integers there are so many possible algorithms you can use, or ways you can easily turn one algorithm into another to suit the problem at hand.

    Instead, try thinking how you would sort an array of structures with each record having both the day of the year a person was born, and their name. You couldn't end up with counting sort because that would make everyone born on the same day of the year have the same name.

    Have you ever written your own hash-table implementation? Bucket sorting is very much like coding a hash-table that uses separate chaining, except that the hash places similiar items near to one another.
    Mr.777 likes this.
    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"

  3. #33
    Registered User
    Join Date
    Sep 2010
    Posts
    90
    Aron, I learn better by example and it works for me.
    ... 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.
    You can bet all that I read, I write and search google for Asm and C++ code for MANY, MANY days before I ask anyone for help. Sometime we have to hit one knee.

    I found that wiki weeks ago, along with hundreds of others documentation and most all of them only provide lip service (enough theory to worry you sick) and I proved that in this thread. There is no programming language on earth that don't provide working examples, to share. Coding is not a secrete anymore for the CIA and KGB to fight over. There are thousands of broken C++ Bucket Sort code on the INTERNET with near exact syntax as what I came up with and every single one of them claim to be a Bucket Sort and so does the people who try to help them fix their broken code at many, many forum around the world. Look at the JAVA link I posted. It has the full-source that will comply and run!!! Between that and over many broken C++ examples of the same coding style, I got hip. I even tried to match the names Count, length etc, while comparing JAVA with the most similar broken C++ files to make it more understandable tome so I can experiment with ease. I use ABC instead of I-O-Jay so I can C.

    I hope you guys don't think I'm trying to be rude but what is holding you up from posting what you think a real bucket sort is suppose to be other than theory? If all you have is theory, please say so, so that some of use can go back to work, knowing that it is actually a real C++ issue.


    Okay, sharris, you have 53 posts; you should know better by now. How has someone not told you?
    sharris Join Date: Sep 2010: tiny 53 100% useful

    You mean someone is counting. This only make me think, how many post do it take to make an c++ expert like you ... THOUSANDS.

    phantomotap Join Date: Jan 2008 Posts: 1,147 80% useless

    I'm just kidding if your are.

    Always copy and paste the code you are actually working with. That code wouldn't even compile so commenting on the idea implemented is pointless.
    Soma
    Why are you here with no code? This is a C++ coding forum, correct? Anyway, the code do work but something is funny so I will make sure it is fixed and I will replace it in a few hours.

    Btw: You sound sarcastic for someone who never entered any of my thread.. Obviously, all of the facts (pros and cons) that I posted must have touch a nerve. Reality is not my fault.

    This is about the lead code I posted. C++ is about code re-use if you have no idea where to start at own your own. Is this correct? I worked with and studied this code very well. Although it did not work but it did give me a clue. Than an solution/idea for the next day:

    Code:
    Writen by a person of positive concern:
    
    The algorithm description and pseudo code are here: http://en.wikipedia.org/wiki/Bucket_sort
    
    So far you've create an array of int filled with random values to be sorted. That's good.
    
    You've printed the array, so you can see the unsorted values. That's good.
    
    You've called BucketSort to sort your data. That's good.
    
    You don't print the sorted array after calling BucketSort. That's bad. It's just the same code that prints the unsorted array.
    
    BucketSort doesn't sort. That's bad. You need to understand the algorithm and implement it. There's plenty of help in the Wikipedia link. You need to decide how many buckets you're going to use apriori, you don't create a bucket for each element. You probably need just 2 or 3 for a 10 element list.
    Last edited by sharris; 03-17-2011 at 10:01 PM.

  4. #34
    Programming King Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Middle of NoWhere
    Posts
    320
    So, if you really understood it, why are you getting hyper?
    Everyone tried to help you in every manner they could.
    Everyone, just get a life...
    And sharris, posts counting doesn't mean anything.... You are not only supposed to post your problems here but to help others as well. If you think, you can, go for that.
    And i think no one can guide you without the real code you are working on.
    So, that's nice if you got idea and concept. Go forward, develop it and in case of any problem, post that here and everyone will try to help you.

    Good luck..
    I don't care if someone doesn't like me, i was not put on earth to entertain everyone.

    No King, no Queen, I am the ACE of battle.

  5. #35
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,217
    Anyway, the code do work but something is funny so I will make sure it is fixed and I will replace it in a few hours.
    I'm well aware that the last code you posted is "funny". It has syntax errors; it would not compile if you were inclined to try. It also has logic errors as was pointed out.

    Oddly enough, I was giving you the benefit of the doubt and assumed that you had working source on your computer and just trashed it in the process of posting it to the forum. I honestly couldn't care how you take it, but typing code into the little browser window wastes the time that these people trying to help you have offered.

    If, on the other hand, that is the source you are working from, I completely agree that you should have posted it as it stands.

    *shrug*

    Code:
    int main(){return(0);}
    There, I've posted code. It hasn't changed anything. Always copy and paste code; never type it in.

    Soma

  6. #36
    Registered User
    Join Date
    Sep 2010
    Posts
    90
    Mr.777
    Everyone tried to help you in every manner they could.
    manner... Were happy over here and may have big plans to share with the world.

    Everyone, just get a life...
    Did you read my post 777, I all ready ask that there be no flame throwing.

    And sharris, posts counting doesn't mean anything....
    Are you talking about our new vistior. He had to be joking or having a bad day.

    You are not only supposed to post your problems here but to help others as well.
    I dish out as much code as I receive since 1999. And yes, I'm not saying who I am of that world because praises don't turn me on. C++ is no super deal but it might have a place as my 3th language if there not to much build-in crap that i can't touch. I made that clear from day-1.

    If you think, you can, go for that.
    Me go for what? Kind of sounds like pointing the finger at the OP instantly. Even a common person doing jury-duty would immediately have concerns about something that came on as strange. I think it's called common since.

    And i think no one can guide you without the real code you are working on.
    Algorithm? Son, there are only a hand full of true algorithm that are used for type programming language... Everything else is what one choose to write or use or claim his own. Every coder would like to re-invent the wheel. But Dollar Bill got it all sew up.


    So, that's nice if you got idea and concept. Go forward, develop it and in case of any problem, post that here and everyone will try to help you.
    Go forward... now I understand why so many "777 Like This" is on this thread. It break my heart that the OP never got a hello until now...

    777, as I said, all is well here and my question will forever stand ...

    I hope you guys don't think I'm trying to be rude but what is holding you up from posting what you think a real bucket sort is suppose to be other than theory? If all you have is theory, please say so, so that some of US can go back to work, knowing that it is actually a real C++ issue.

    btw for the record I never had the kind of "problem" that are you speaking of. I only have a problem when it's all about talk and no show and tell or truth. Who would ask for less.

    Well, I guest I'll go back to work. Sorry if anyone else is having problem the code. I would never leave broken code on the INTERNET so others can find and unknowingly pollute the world for even more new users of C++. I will find the problem and fix it and show more I hope, if given a minute or three. Is it count or is it bucket. For me, all I need is to see the code that saids "this is it", what can you do for me! If not, simply move on or foward

    darn, all of this time wasted editing bad mouth. bad spelling, etc. Will it ever end.

    Have a great day!
    Last edited by sharris; 03-18-2011 at 12:53 AM.

  7. #37
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I found that wiki weeks ago, along with hundreds of others documentation and most all of them only provide lip service (enough theory to worry you sick)
    There is a reason why Wikipedia usually provides only pseudo-code for algorithms. If it were to provide, for example, C++ code for a bucket sort, then it would necessarily contain language-specific details (e.g how do I allocate memory? how do I handle out-of-memory?) which can only distract one from learning what the algorithm is all about.

    Unfortunately, it seems the pseudo-code on Wikipedia isn't particularly good either, in that article. The FOR-loops seem to be borrowed from BASIC language, bringing in a distracting BASIC-specific detail (looping until length - 1). Perhaps someone good with conventional pseudo-code can edit that.

    As to the link, too bad there's a whole page selling counting sort to you under the name of bucket sort

    But again, the purpose of this board is not to provide ready-made code for askers, so that they can learn from example, or just hand it in as their homework.

    We can explain you the algorithm or help you fix your code.
    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).

  8. #38
    Registered User
    Join Date
    Sep 2010
    Posts
    90
    We can explain you the algorithm or help you fix your code.
    DEAL! I know this forum got it reasons and it really don't matter. What all you guys done for me I am a better C++ coder. This subject is for expert C++sors really. My only goal is Vector, MAP and it, as my hobby and work. I got enough docs to read until QUANTUM arrive, and have. I just need to know what the C++ algorithm looks like. I am a expert assembler for over 12 years just like you guys are expert C++sor. All we got to do is look at an algorithm, clean it up, pop it in, add some code or a debugger so you can see how it works, than clock it for comparison to others, and not a darn thing else. It just takes me longer for C++ but I will master it the day it all kick-in. I had all of this code on my machine from months ago. Know some JAVA, google and read into this forum or few if you really want to learn C++ fast. I had it all the time and forgot about em. I got over a 60,000 examples in ASM that I use, repaired or wrote so I care nothing of homework. Final noobish question:: Is once or both of these the this the real McCoy? I am in no rush. Need the full source? Let just me know. Btw; 10 out of 10 this site disable the code above. Don't ask me to prove it. I also have it on the net elsewhere and the same code works! Want the link, PM me.

    1)
    Code:
    void bucketSort(int *inArr, int arrSize, int variance){
      int *bucket = (int*)malloc(sizeof(int) * variance);  
      // Initialize all bucket nodes to have a count of 0
      memset(bucket, 0, sizeof(int) * variance);
      // Throw the count of each node into the bucket
      for (int i = 0; i < arrSize; i++){
        bucket[inArr[i]]++;
      }
      // We'll fill the new array with whatever is in the bucket
      int newArrayPosition = 0;
      for (int x = 0; x < variance; x++){
        for (int j = 0; j < bucket[x]; j++){
          inArr[j + newArrayPosition] = x;  
        }
        newArrayPosition += bucket[x];
      }
     
      free(bucket);
    }


    2)
    Code:
    void BucketSort (unsigned int a [], unsigned int n)
    {
        int buckets [m];
    
        for (unsigned int j = 0; j < m; ++j)
    	buckets [j] = 0;
        for (unsigned int i = 0; i < n; ++i)
    	++buckets [a [i]];
        for (unsigned int i = 0, j = 0; j < m; ++j)
    	for (unsigned int k = buckets [j]; k > 0; --k)
    	    a [i++] = j;
    }
    I don't plan to move on, I plan to go forward.

  9. #39
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Sure it works. It's just not bucket sort If your aim is to get data sorted, then it's fine.

    Ok, here's how bucket sort could be implemented in Python. The non-obvious lines are commented. The whole code can be translated line by line to C++. Note, std::vector is closer to the list type (things in square brackets).

    Code:
    #this functions sorts numbers in range 0...99
    def bucket_sort(data):
        buckets = [[] for x in range(10)] #list of ten empty lists
    
        #place data into buckets    
        for item in data:
                buckets[item / 10].append(item)
    
        #sort buckets
        for bucket in buckets:
                insertion_sort(bucket)
    
        #write sorted array to output            
        i = 0
        for bucket in buckets:
                for item in bucket:
                    data[i] = item
                    i += 1
    
    def insertion_sort(data):
        i = 1
        while i < len(data):
                value = data[i]
                j = i - 1
                while j >= 0 and value < data[j]:
                        data[j + 1] = data[j]
                        j -= 1
                data[j + 1] = value
                i += 1
    
    if __name__ == '__main__':
        from random import randint
        #generate some random data
        array = [randint(0, 99) for x in range(20)]
        print array
        bucket_sort(array)
        print array
    Here's a link to where you can execute it online.
    Last edited by anon; 03-18-2011 at 03:17 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).

  10. #40
    Registered User
    Join Date
    Sep 2010
    Posts
    90
    could be implemented
    in Pythonnnnnn. So it's hands down ... so there is no true bucketSORT for C++ Heehee.

    And you know for a fact that these algorithm are not true bucketSORT... It's not your fault. I believe you.
    Last edited by sharris; 03-18-2011 at 04:31 PM.

  11. #41
    The larch
    Join Date
    May 2006
    Posts
    3,573
    there is not true bucketSORT for C++ Heehee.
    What's your problem? The only difference is the syntax. Translate each line to a line of C++ that has the same effect and you'll have it.
    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. #42
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,661
    Quote Originally Posted by sharris View Post
    in Pythonnnnnn. So it's hands down ... so there is no true bucketSORT for C++ Heehee.
    Bucket sort is not a language specific algorithm. It's barely implementation specific.

    The entire algorithm is rather concisely put as three steps:
    1) separate your data into buckets
    2) sort the buckets
    3) visit each bucket to rebuild your sorted data

    If bucket sort was the right sort to use, step three is what makes the data sorted. You made buckets for each of the finite possibilities there were among the data to sort, and arranged those possibilities in order when you performed step three.

    To say that there isn't a bucket sort in C++ is like saying there isn't a heap sort in C++. You can implement a bucket sort in C++ like you could implement a heap sort in C++. There just isn't going to be a ready-made function that works for all uses of bucket sort.

    Quote Originally Posted by sharris
    And you know for a fact that these algorithm are not true bucketSORT... It's not your fault. I believe you.
    He's got the right idea, even if it isn't JUST a bucket sort. The problem is, you want an example using a list of integers, which doesn't really call for bucket sort by itself. It isn't going to be the best example. I said it earlier: you can use bucket sort to sort all kinds of weird things, like employees by position. It doesn't necessarily make sense to sort by position with a comparison. "President" comes before "Peon" but you can't sort based on title, it's the wrong order. You could assign individual employees a weight to serve as a position marker and then sort by that, but that's not optimal. But you can make buckets for positions, and arrange the data however you want in the "visiting" step.

    When implementing bucket sort, you might ask what data structure buckets should be -- I said associative array earlier, and iMalc said that a hash table with separate chaining is an option -- so that's all rather specific. You just need to think about what kind of STL objects will give this "bucket" functionality to you.
    Last edited by whiteflags; 03-18-2011 at 05:23 PM.

  13. #43
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by Elysia View Post
    Ah. There is probably some proof of this, not that I am too interested, but who says we cannot find such a solution in the future?
    Clearly, this is not possible with today's algorithms, but the future...?
    I don't have a rigorous proof, but I know the rough idea (a rigorous one would probably be too verbose and technical anyway).

    Basically, when you can only use binary comparisons to inspect the data, you must perform at least one operation for every bit of information you extract from the data. For N distinct elements, the algorithm must choose which of the N! permutations arranges the elements into sorted order. This choice of one from N! possibilities must come from information in the data, and a choice of one from N! contains log_2_(N!) bits of information. Hence, log_2_(N!) bits must be extracted from the data, and at least log_2_(N!) operations must be performed.

    There is this thing called Sterling's approximation, which says N! ~ sqrt(2 * pi * N) * (N / e) ^ N, which means O(N!) = O((N / e) ^ N). From here it's just a bit of manipulation:

    O(min operations) = O(log_2_(N!))
    = O(log(N!))
    = O(log((N / e) ^ N))
    = O(N log (N / e))
    = O(N * (log(N) - log(e)))
    = O(N log(N)) - O(N log(e))
    = O(N log(N))

  14. #44
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Okay so there's no C++ code for bucket sorting an array on the internet, according to the search engine you used...
    I gave in and decided to do a search of my own, and what popped up as the first search result: Bucket Sort in C++

    What's next, no p0rn on the internet either?
    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"

  15. #45
    Registered User
    Join Date
    Sep 2010
    Posts
    90
    Finally, something to learn from that really is a bucketSorter. Only you deserve to be so lucky to find the only one on planet Earth written in Pure C++. Thank GOD!!! I see it's build using <template>, so that was the idea behind Elysia example. All others I found, you seen, were only loops-counters with the word bucket as its label. It was difficult following instructions posted here while using these codes to serve as my visual map. That's why I ask for working examples so one can have something feasible to work with, then we gut the code to learn more.

    There may be one more real-bucketSorter that I found though a link with-in or through your homepage, days ago. I did play with this code but drop it for some reason. Is this a realMcoy also?
    C++ Source Code

    ....
    ....
    I missed your post and just read it whiteflags. Now I think I get the full picture. This would be something to use in an major application if needed and it's up to the implementor to create what he is after based on the idea of bucketSorter. This could be an major operation if one choose to go this route. There is no magic. Just pure logic. That's what real coding is all about and it can be fun!

    Hope I did not miss your point this time whiteflags

    After this bucketSorter thing, soon I'll be able to recognize what a C++ algorithm can or cannot do by sight just like most of you guys do. I found my new goal.
    Last edited by sharris; 03-19-2011 at 11:17 AM.

Page 3 of 4 FirstFirst 1234 LastLast
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-19-2001, 11:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21