C++で8個のソート済みリストをマージするアルゴリズムを使用する必要があります

Question

私はソート済みリストを1つにまとめなければならない8個のソート済みリストがあります。私はこれを行うための最善の方法を知らない。私は次のことを考えていました：

void merge_lists_inplace(list<int>& l1, const list<int>& l2) 
{ 
    list<int>::iterator end_it = l1.end(); 
    --end_it; 
    copy(l2.begin(), l2.end(), back_inserter(l1)); 
    ++end_it; 
    inplace_merge(l1.begin(), end_it, l1.end()); 
} 

list<int> merge_8_lists(list<int>[8] lists) 
{ 
    merge_lists_inplace(lists[0], lists[1]); 
    merge_lists_inplace(lists[2], lists[3]); 
    merge_lists_inplace(lists[4], lists[5]); 
    merge_lists_inplace(lists[6], lists[7]); 

    merge_lists_inplace(lists[0], lists[2]); 
    merge_lists_inplace(lists[4], lists[6]); 

    merge_lists_inplace(lists[0], lists[4]); 

    return lists[0]; 
} 

しかし、最後にソートすることを心配する方が良いでしょうか？

list<int> merge_8_lists(list<int>[8] lists) 
{ 
    for (int i = 1; i < 8; ++i) 
     copy(lists[i].begin(), lists[i].end(), back_inserter(lists[0]));   
    lists[0].sort(); 
    return lists[0]; 
} 

サイドノート：リストが変更されても構いません。

Answer 1

マージソートのマージフェーズの簡単な拡張は、priority queue（たとえば、heap）を使用して、O（n lg m）時間（nはアイテムの総数、mはリストの数）でこれを行うことができます。擬似コード：

Let P = a priority queue of the sorted lists, sorted by the smallest element in each list 
Let O = an empty output list 
While P is not empty: 
    Let L = remove the minimum element from P 
    Remove the first element from L and add it to O 
    If L is not empty, add L to P 

そして、C++での簡単な（未テスト！）具体的な実装：

#include <list> 
#include <set> 

template<typename T> 
struct cmp_list { 
    bool operator()(const std::list<T> *a, const std::list<T> *b) const { 
     return a->front() < b->front(); 
    } 
}; 

template<typename T> 
void merge_sorted_lists(std::list<T> &output, std::list<std::list<T> > &input) 
{ 
    // Use a std::set as our priority queue. This has the same complexity analysis as 
    // a heap, but has a higher constant factor. 
    // Implementing a min-heap is left as an exercise for the reader, 
    // as is a non-mutating version 
    std::set<std::list<T> *, cmp_list<T> > pq; 

    for (typename std::list<std::list<T> >::iterator it = input.begin(); 
      it != input.end(); it++) 
    { 
     if (it->empty()) 
      continue; 
     pq.insert(&*it); 
    } 

    while (!pq.empty()) { 
     std::list<T> *p = *pq.begin(); 
     pq.erase(pq.begin()); 

     output.push_back(p->front()); 
     p->pop_front(); 

     if (!p->empty()) 
      pq.insert(p); 
    } 
} 

Answer 2

あなたがリストのそれぞれに一度にマージソート1を適用してみてください：

http://en.wikipedia.org/wiki/Merge_sort

これは、マージソートのアルゴリズムを持っています。本質的には、リスト1と2を使い、ソートしてマージします。次に、その新しい結合リストを取り出し、リスト3でソートします。これは、完全にソートされたリストが1つあるまで続きます。

EDIT：あなたのリストがすでにソートされているので、

実際には、マージソートの最後の部分のみが必要とされるであろう。私は反復的に大きなリストと大型のリストを結合しながら、より大きなリストのそれぞれを並べ替えることができます。あなたの完全なリストは本質的に、分割と征服のアプローチで終わった後のマージソートです。

Answer 3

パフォーマンスが懸念されていない場合、私は最後のリストを並べ替えます。コードは、より読みやすく、短く、将来コードを見直す人に嫌われる可能性は低いです。

Answer 4

これは標準（8方向ですが）マージソートです。

基本的にあなたがして、最低値を毎回抽出し、それらを処理するような何か始める8つのソートされたリストを "開く"：

# Open all lists. 

open newlist for write 
for i = 1 to 8: 
    open list(i) for read 
end for 

 

# Process forever (break inside loop). 

while true: 
    # Indicate that there's no lowest value. 

    smallidx = -1 

    # Find lowest value input list. 

    for i = 1 to 8: 
     # Ignore lists that are empty. 

     if not list(i).empty: 
      # Choose this input list if it's the first or smaller 
      # than the current smallest. 

      if smallidx = 1: 
       smallidx = i 
       smallval = list(i).peek() 
      else: 
       if list(i).peek() < smallval: 
        smallidx = i 
        smallval = list(i).peek() 
       end if 
      end if 
     end if 
    end for 

 

# No values left means stop processing. 

    if smallidx = -1: 
     exit while 
    end if 

    # Transfer smallest value then continue. 

    smallval = list(smallidx).get() 
    newlist.put(smallval) 
end while 

Answer 5

を

基本的には、マルチウェイ・マージーソートの一部CEPT自分のものはすでにただ、各アレイ内の最低を見つける（ほとんどのスタックとして使用）と、すべてのスタックが空であるまで、あなたの出力にそれを置く...

http://lcm.csa.iisc.ernet.in/dsa/node211.html

をソートされ...

Answer 6

ますほしいa merge sort。あなたのリストはすでに分割されていますが、最小のレベルまではありません。あなたはこれを実行することもできます。

連結は、リスト内の最後のノードから次のリストの最初の要素へのリンクを追加する必要がありますので、時間のかかる作業/メモリであってはならない

unsorted_list = concatenate(list[0], list[1], list[2], ... , list[7]); 
sorted_list = merge_sort(unsorted_list); 

。