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; Originally Posted by anon Elysia, I think using numeric_limits<T>::max is highly problematic (value might be too large to allocate, not ...

  1. #16
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,538
    Quote Originally Posted by anon View Post
    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 View Post
    ...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.
    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.

  2. #17
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by Elysia View Post
    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).

  3. #18
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,538
    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...?
    Mr.777 likes this.
    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.

  4. #19
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,594
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #20
    Programming King Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Middle of NoWhere
    Posts
    320
    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....
    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.

  6. #21
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,659
    Yeah, the only hope would be quantum based computing, which stands to make things better as much as it could make things worse.

  7. #22
    Programming King Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Middle of NoWhere
    Posts
    320
    So, that's not that far although...
    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.

  8. #23
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,594
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #24
    Registered User
    Join Date
    Sep 2010
    Posts
    90
    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];   }  }


    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.

  10. #25
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.

    ... Vector Buckets ... Array Buckets ...
    A vector is essentially a dynamically allocated array, just simpler and safer to work with.
    Last edited by anon; 03-16-2011 at 03:25 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).

  11. #26
    Registered User
    Join Date
    Sep 2010
    Posts
    90
    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,

    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 
    
    }}}
    edit:: bad mouth, math and bad spelling
    Last edited by sharris; 03-16-2011 at 09:27 PM.

  12. #27
    Registered User
    Join Date
    Sep 2010
    Posts
    90
    Nevermind, I'll post the solution tonight, forsure.
    Last edited by sharris; 03-17-2011 at 02:38 PM.

  13. #28
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,659
    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.

  14. #29
    Registered User
    Join Date
    Sep 2010
    Posts
    90
    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.
    Last edited by sharris; 03-17-2011 at 08:30 PM.

  15. #30
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    Last edited by anon; 03-17-2011 at 06:22 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).

Page 2 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