Thread: Bucket Sort or Myth

Originally Posted by anon

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.

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.

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..

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!

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.

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.

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.

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.

Originally Posted by sharris

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.

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.

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?

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.