8 sortierte Listen in C++ zusammenführen, welcher Algorithmus sollte ich verwenden

Question

Ich habe 8 sortierte Listen, die ich in 1 sortierte Liste zusammenführen muss. Ich kenne den besten Weg nicht. Ich dachte an Folgendes:

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]; 
} 

Aber wäre es besser, sich nur um die Sortierung kümmern?

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]; 
} 

Seitliche Anmerkung: Es ist mir egal, dass die Listen geändert werden.

Answer 1

eine einfache Erweiterung der Mischphase die Mischsortierung können dies in O (n lg m) Zeit (wobei n = Gesamtzahl der Elemente, und m = Anzahl der Listen), unter Verwendung eines priority queue (zB ein heap). Pseudo-Code:

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 

Und eine einfache (nicht getestet!) Konkrete Umsetzung in 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

Sie könnten versuchen, die Mergesort einer nach dem anderen auf jede der Listen Anwendung:

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

Dieser den Algorithmus für die Mergesort hat. Im Wesentlichen würden Sie mit Liste 1 und 2 gehen und mergen diese sortieren. Dann würden Sie diese neue kombinierte Liste nehmen und mit Liste 3 sortieren, und dies wird fortgesetzt, bis Sie eine vollständig sortierte Liste haben.

EDIT:

Eigentlich, denn Ihre Listen bereits sortiert sind, wird nur der letzte Teil des Mergesort benötigt würde. Ich würde die Listen iterativ zu immer größeren Teilen kombinieren, während ich jede dieser größeren Listen sortiere, bis Sie Ihre vollständige Liste haben, was im Wesentlichen die Art der Zusammenführung ist, nachdem sie mit ihrem Divide and Conquer-Ansatz fertig ist.

Answer 3

Wenn die Leistung nicht von Belang ist, würde ich die letzte Mal die Listen sortieren. Der Code ist besser lesbar, kürzer und weniger wahrscheinlich, wenn jemand den Code in Zukunft erneut durchsucht.

Answer 4

Dies ist eine standardmäßige (wenn auch 8-fach) Zusammenführungs-Sortierung.

Grundsätzlich Sie "offen" die acht sortierten Listen verarbeiten sie dann beginnen, den niedrigsten Wert jedes Mal zu extrahieren, so etwas wie:

# 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

Grundsätzlich machen Sie einen Teil des Multiway-Mergesort, z cept Ihr Material bereits sortiert ...

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

Nur die niedrigsten (als Stapel verwenden fast) in jedem Array finden und umsetzen, die in Ihrer Ausgabe, bis alle Stapel leer sind ...

Answer 6

Sie wollen a merge sort. Ihre Listen sind bereits geteilt, aber nicht bis zur kleinsten Ebene.Sie können dies tun wollen:

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

, das keine Zeit/Speicher aufwendigen Vorgang sein sollte, weil die Verkettung einen Link aus dem letzten Knoten in einer Liste mit dem ersten Elemente der nächsten Liste hinzufügen soll.