来自包含存储桶的数组中N个排序项的合并 [英] N Way Merge of Sorted Items from an array containing buckets

问题描述

考虑一个由多个存储桶组成的数组，每个存储桶包含一定数量的整数项.例如，array1 [] = {19,23,27,29，14,15,16,17，11,12,15,16}是一个数组，其中包含3个存储桶，每个存储桶中有4个项目.

目的是从每个存储桶中选取最小的元素，取最小的最小值，然后将该最小值整体存储到合并存储桶中，然后重复进行直到所有内容都被排序为止.

我将如何使用数组数据结构或任何可以解决我想要实现的结构的方法，将对您的帮助深表感谢.

到目前为止，这是我正在处理的代码:

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:

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;

推荐答案

无论您是否想要就地解决方案，您都不会确定.我认为不是.

您需要在每个存储桶中保留一个运行索引，知道每个存储桶可以跨越的索引范围.使用一组索引，每个存储区一个.

从所有较低的索引开始.

重复选择当前元素最小的存储桶，输出该元素并增加该存储桶的索引. (当任何索引达到最大值时，请使下一个值为+无限.)

当所有索引都达到最大值时，您就完成了.

为了找到铲斗中最小的元素，您有两个选择:
-如果铲斗数量很少(例如< 10)，则只需线性搜索最小值(跳过耗尽的铲斗)；
-否则为此使用优先级队列，存储具有值/存储区索引的对. http://en.wikipedia.org/wiki/Priority_queue#Usual_implementation [

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.

这篇关于来自包含存储桶的数组中N个排序项的合并的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！