Click here to Skip to main content
15,868,016 members
Please Sign up or sign in to vote.
3.00/5 (1 vote)
See more:
Consider an array made up of several buckets with each bucket containing a sorted number of integer items. For example, array1 [] = {19,23,27,29, 14,15,16,17, 11,12,15,16} is an array with 3 buckets and 4 items in each bucket.

The aim is to pick the minimum element from each bucket, take the minimum of the minimum and store that minimum value overall into a merge bucket and repeat until all are sorted.

Your help would be much appreciated as to how I may do it with an array data structure or any structure that will solve what I'm trying to achieve.

So far this is my code which I'm working on:

C#
vector<int>sorted_bucket;
    int num_items =12;
    int array1 [] = {19,23,27,29,  14,15,16,17,   11,12,15,16};

    int *arr_begin = new int [num_items];
    int *arr_end = new int [num_items];
    int currentItem_arr1 = 0;
    int currentItem_arr2 = 0;

    //putting elements in arr_begin
    for(int i = 0; i < 12; i += 4)
    {
        arr_begin[currentItem_arr1] = array1[i];
        cout<<"This is arr_begin[i] "<<arr_begin[currentItem_arr1]<<endl;
        currentItem_arr1++;
    }

    cout<<"\n"<<"Elements in arr_end"<<endl;
    //putting elements in arr_end
    for(int i = 3; i < 12; i += 4)
    {
        arr_end[currentItem_arr2] = array1[i];
        cout<<"This is arr_end[i] "<<arr_end[currentItem_arr2]<<endl;
        currentItem_arr2++;
    }

    int j=0;
    int t = 1;
    int min = arr_begin[2];
    while (num_items > 0)
    {


        //Array size is Number of Items / Number of Threads
        int p = 0;
        while(p < 3)
            {
                if (min > arr_begin[p])
                {
                    min = arr_begin[p];
                    j = p;
                    cout<<"The real J "<<j<<endl;
                }
                p = p + 1;
                //j = p;
            }


            sorted_bucket.push_back(min);

            arr_begin[j] = array1[4*j + 1];


            num_items = num_items - 1;
            min = arr_begin[2];
    }

    cout<<"Sorted Items "<<endl;
    for (int i = 0; i < 12; i++)
    {
        cout<<sorted_bucket[i]<<endl;
    }

    return 0;
Posted
Comments
Richard MacCutchan 30-Oct-12 16:57pm    
Why not use a separate array for each bucket, or a 2D array? What you have coded is a single array of 12 values. Also if you change the length of your array or of your buckets, you need to go through all your code changing the hard coded length values. Use the features of the compiler to make your life easier.
Sergey Alexandrovich Kryukov 30-Oct-12 19:06pm    
When you say "buckets", do you mean implementing of key-based dictionary of hash map functionality?
--SA
Santhosh G_ 31-Oct-12 0:02am    
Is it bucket sort algorithm implementation?
http://en.wikipedia.org/wiki/Bucket_sort

1 solution

You don't specity if you want an in-place solution or not. I assume not.

You need to keep one running index per bucket, knowing the range of indexes that every bucket can span. Use an array of indexes, one per bucket.

Start with all indexes in their lower value.

Repeatedly pick the bucket where the current element is the smallest, output this element and increase the index of this bucket. (When any index has reached its highest value, make as if the next value was + infinity.)

You are done when all indexes have reached their highest value.

In order to find the smallest element amont the buckets, you have two options:
- if the number of buckets is small (say < 10), just use a linear search for the minimum (skipping the exhausted buckets);
- otherwise use a priority queue for this purpose, storing pairs with value/bucket index. http://en.wikipedia.org/wiki/Priority_queue#Usual_implementation[^]. Implementation details are more involved.
 
Share this answer
 
Comments
wayten 2-Nov-12 9:06am    
Thank you for your comments. This was very helpful.
YvesDaoust 2-Nov-12 9:30am    
You are welcome. You can rate my post then.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900