# Bucket Sort or Myth

Show 80 post(s) from this thread on one page
Page 2 of 4 First 1234 Last
• 03-16-2011
Elysia
Quote:

Originally Posted by anon
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?

I know. I thought about it, but it would basically add + O(N) sorting time, so I opted not to for this example.
For small integer sorts, this is definitely practical and fast.
But sure, you could always make your own example to demonstrate the point or make a real bucket sort. I don't think if I'm for such a challenge at the moment...

Quote:

Originally Posted by Mozza314
...It's impossible to sort N distinct values in O(N) time...

Erm, I take it that means if I have N items, the values of those numbers are 0...N-1. If so, then it is very possible to sort in O(N) and my sorting example points that out very well.
• 03-16-2011
Mozza314
Quote:

Originally Posted by Elysia
Erm, I take it that means if I have N items, the values of those numbers are 0...N-1. If so, then it is very possible to sort in O(N) and my sorting example points that out very well.

Ah, you got me there. Let me say it more rigorously - it's impossible for an algorithm, using only binary comparisons to inspect its data, to sort N randomly arranged distinct elements in an average number of operations less than O(N log N).
• 03-16-2011
Elysia
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...?
• 03-16-2011
laserlight
Quote:

Originally Posted by Elysia
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...?

If there is a proof, then it says that we cannot find such a solution in the future since it pertains to comparison based sorting algorithms, not to any particular sorting algorithm. I have always just taken the literature's word that this is proven, but a quick search brings up this PDF document on Comparison-based Lower Bounds for Sorting.
• 03-16-2011
Mr.777
Sorry for interuption but i am agree to what Elysia has said.
By looking to the enhancements of programming concepts, i am damn sure that in very near future, everything that seems impossible today, will be possible.
As almost one century ago, no one even thought about the computer but today, everyone is using and playing with it. At that time people used to say that this is not even possible but science has proved it.
Be a little optimist and everything will get solutions in very near future....
• 03-16-2011
whiteflags
Yeah, the only hope would be quantum based computing, which stands to make things better as much as it could make things worse.
• 03-16-2011
Mr.777
So, that's not that far although...
• 03-16-2011
laserlight
Quote:

Originally Posted by Mr.777
Sorry for interuption but i am agree to what Elysia has said.
By looking to the enhancements of programming concepts, i am damn sure that in very near future, everything that seems impossible today, will be possible.
As almost one century ago, no one even thought about the computer but today, everyone is using and playing with it. At that time people used to say that this is not even possible but science has proved it.
Be a little optimist and everything will get solutions in very near future....

For any given problem, there is a minimum amount of work that must be done to solve it. Using a quantum computer will not change this. However, where feasible you could change the parameters of the problem, and hence get a different lower bound if you are not constrained to use a comparison based sorting algorithm.
• 03-16-2011
sharris
I think I'm going places :) If things goes well I'll have a Vector Buckets program up and running by morning because this Array of Buckets is going to get me there. Since Array of Buckets is more common I went for it first. The only problem seems to be my math. This line seem to be the problem. I got the clue from the code that is commented out at the bottom of the page. Could someone show me how to correct this. Thanks in advance.

Code:

`for (int div = 1; div <= size / 2; div++) {`
....
....

Code:

```#include <iostream> #include <cstdlib> #include <ctime> using namespace std; void BucketSort(int a[], int size); int main() {     const int size = 10;     int data[size];     srand(119523);       for (int i = 0; i < size; i++) {         data[i] = rand()% 100;     } // .......................................     cout << "Original  order  :";     for (int i = 0; i < size; i++) {         cout << "  " << data[i];  }     cout << endl;     cout << endl; // .......................................     cout << "After Bucket sort:";     BucketSort( data, size );     cout << endl;     cout << endl; system("pause"); } void BucketSort(int a[], int size) {     int *ptr[10];                            //  Array of 10 pointers     int pcount[10];                          //  Array of 10 counters     for (int i = 0; i < size; i++) {        //  Alloc space For each pointer,         ptr[i] = new int[size];     }      //  bool done = false;  //  for (int div = 1;  !done;  div *= 10) {  // indexvalue = (a[i]/div) % 10       for (int div = 1; div <= size / 2; div++) {           cout << "  " << a[div];  }  }```

Quote:

I'm a tad disappointed if my own site didn't register as a source of bucket sort code on google.
iMalc, your site will be my 2nd home.

.co is like have a facebook page. Google don't play that. If I were you I would give NetworkSolution or equivalent the whole \$34.99 every year for a .com name... Forget about anything cheaper. If that company go out of business it is possible that your domain could be made available to others with-out your knowledge. Who knows! But one thing for sure, AT&T and NetworkSolution would be the last to close their doors.
• 03-16-2011
anon
I'd suggest initializing this:

Code:

`    int pcount[10] = {0};`
Code:

`for (int div = 1;  !done;  div *= 10) {  // indexvalue = (a[i]/div) % 10`
Not sure what you mean with this.

IMO, what you need to do is to look at each item in the input, determine which bucket it falls into ( data[n] / 10) and put it there, incrementing the respective pcount.

Next you'd need to sort each bucket. Wikipedia mentions insertion sort.

Then you copy the values from each bucket back into the input array.

Quote:

... Vector Buckets ... Array Buckets ...
A vector is essentially a dynamically allocated array, just simpler and safer to work with.
• 03-16-2011
sharris
So it's true, you can't drag a dead elephant to the water and make him drink.

Search results - LiteratePrograms
No article with exactly the supplied title exists. You can [[:Bucket sort C++|create this article]].

Bucket sort (PHP) (1840 bytes)

Bucket sort (Java) (2054 bytes)

Bucket sort (C) (2023 bytes)

Bucket sort (Python) (1752 bytes)

But no C++

Bucket sort - Wikipedia, the free encyclopedia
... and still, no C++

I even got use to the curl-braces. Now that I know QUANTUM is nearing I got another job for em.

....
....

Thank anon,

Quote:

Code:
for (int div = 1; !done; div *= 10) { // indexvalue = (a[i]/div) % 10
Not sure what you mean with this.
I never cross-links unless the board don't mine, sometimes. Credit is due. I got to make a pot of coffee or else blow the whole night. Here's his entire master-piece, un-cut ... not totally design for the never-never lands :)

Code:

```#include <iostream> #include <ctime> using namespace std; // The prototype for a sorting function void BucketSort(int array[], int size); void BucketSortDummy(int array[], int size);                // added int main() {     const int array_size = 17;     int int_arry[array_size];     // For continued testing: use a different seed each time     //srand(time(NULL));     // During program development, use the same seed each time     // so that you can see exactly what happens differently     // as you change your program.     srand(87654321);     // For testing, I will use integer values 0-99     for (int i = 0; i < array_size; i++) {         int_arry[i] = rand()% 100;     }     cout << "Initially :";     for (int i = 0; i < array_size; i++) {         cout << "  " << int_arry[i];     }     cout << endl;     BucketSortDummy(int_arry,array_size);                // added     cout << "After sort:";     for (int i = 0; i < array_size; i++) {         cout << "  " << int_arry[i];     }     cout << endl; //........................................  added by me ... minor change     BucketSort(int_arry,array_size);     cout << "After sort:";     for (int i = 0; i < array_size; i++) {         cout << "  " << int_arry[i];     }     cout << endl; //........................................ system("pause");                        // added .. remove this if you like } // You can put the source for BucketSort() here or in another file void BucketSortDummy(int array[], int size)            // minor change added {     // Do nothing for now! } void BucketSort(int a[], int size) {     //Declare an array of ten pointers to int     int *b[10];     /*       Declare an array of ten counters that keep track       of how many ints each b[] array contains at       the end of each loop     */     int bcount[10];     /*         For each pointer, allocate storage for "size" ints:         so that we will have ten arrays:         b[0] is an array of "size" ints         b[1] is an array of "size" ints         .         .         .         b[9] is an array of "size" ints     */     for (int i = 0; i < size; i++) {         b[i] = new int[size];     }     /*         We will start with a divisor of 1.  Each successive time through the         loop, we will multiply the divisor by 10.         For each element a[i], The digit being used to as an index will be             indexvalue = (a[i]/divisor) % 10         So, the first time through the loop we get the units digit,             the next time we get the hundreds digit,             the next time we get the thousands digit,             .             .             .         Here's the big loop:             Go through a loop over elements of a[], and store elements in the             b[indexvalue] array.             Have a counter for each b[] array that keeps track of how many             elements have been copied there.             Go through a loop over the b[] arrays.  For each array copy elements             back to the a[] array.  If there are any elements in any b[] array             other than b[0] we go to the top again.         How do we know when we are through with the big loop?         When all of the elements are end up in b[0] and the other         buckets are empty.     */         // Here's the big loop:     bool done = false;     for (int divisor = 1; !done; divisor *= 10) { //Begin the Big Loop {           cout << "  " << a[divisor];;    //  added - this was my first try                                             //  old first try }}}```
• 03-17-2011
sharris
Nevermind, I'll post the solution tonight, forsure.
• 03-17-2011
whiteflags
Quote:

Bucket sort (PHP) (1840 bytes)

Bucket sort (Java) (2054 bytes)

Bucket sort (C) (2023 bytes)

Bucket sort (Python) (1752 bytes)

But no C++
I guess if C++ is the only language you understand, it would be hard to learn from those. I think you need to spread out, once you've solved enough problems to be comfortable with C++'s features so that more references make sense to you. I've done far from everything in C++, yet I know more than one language now.
• 03-17-2011
sharris
whiteflags, I see what you mean and glad you understand. I'm so happy I'm taking a JAVA course this semester. It's helping me to understand C++ ten time better every week. Now I get it ...

Code:

```//        http://en.literateprograms.org/Bucket_sort_(Java) //        BucketSort Array #include <vector> #include <iostream> #include <cstdlib> #include <ctime> using namespace std;  void bucketSorter(int DATA[],int length, int COUNT);   int main() {         int DATA[]    =    {90, 90, 90, 80, 70, 60, 50, 40, 30, 30};         int element  =    sizeof(DATA)/sizeof(int);         int COUNT    =    DATA[0]; // .......................................     cout << "Original  order  :";     for (int i = 0; i < element; i++) {         cout << "  " << DATA[i];  }     cout << endl;     cout << endl; // .......................................     cout << "After Bucket sort:";         bucketSorter(DATA, element, COUNT);         getchar(); } //  .............................................. //  .............................................. void bucketSorter(int DATA[],int length, int COUNT)     {     int* bSort = new int[COUNT];     int SIZE = length;     for( int B  = 0  ;  B <= COUNT ;  ++B )  {           bSort[B] = 0; }     for(int A = 0 ; A < SIZE ; ++A)          {           ++bSort[DATA[A]];  }            for( int A = 0, B = 0  ;  B <= COUNT  ; ++B )  {           for(int C = bSort[B]  ;  C > 0  ;  --C )  {                                       DATA[A++] = B;  } }  //  it matters here A++ not ++A     for( int A = 0  ;  A < SIZE  ;  ++A )         {         cout << "  " << DATA[A];     }                cout << endl; }```
This is my code and it do work! ... but when I cup and paste it from this link, it don't work so I don't know who has a possible bug.
• 03-17-2011
anon
Again, this seems to be a counting sort.

A counting sort is where you count how many of each value you have. Here you count that you have three 90s, one 80 etc. Then you write as many values of each back into the input array.

A bucket sort is where you split data into smaller groups.

For example, unsorted data is {22, 12, 7, 5, 16, 20, 26}.
You choose to use 3 buckets: one for values 0-9, another for 10-19, and third for 20-29.
Now you put each item into a suitable bucket, and have those buckets contain {7, 5}, {12, 16}, {22, 20, 26}.
Then you sort each of those buckets (for example with insertion sort), and end up with {5, 7}, {12, 16}, {20, 22, 26}.
Then you write the contents of all buckets back to input array and get {5, 7, 12, 16, 20, 22, 26}. The array is now sorted.

I think you have hard times determining whether you have problems with C++ syntax or with getting the point of the algorithm.
To get the idea how the algorithm works, the Wikipedia page should be entirely enough.
Then you figure out how to translate that idea into C++ code (or any other language). If you just search for ready-made code, then you'll miss a lot of the learning experience.

----------

BTW, you don't seem to be aware that bSort[90] will be out of bounds in your program, and if it doesn't crash, then it is just a coincidence. Besides, by COUNT you probably mean LARGEST_VALUE.
Show 80 post(s) from this thread on one page
Page 2 of 4 First 1234 Last