Scalanie 8 posortowanych list w C++, który algorytm powinienem używać

Question

Mam 8 posortowanych list, które muszę scalić w jedną posortowaną listę. Nie wiem, jak to zrobić najlepiej. Zastanawiałem się, co następuje:

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

Ale czy lepiej będzie po prostu martwić się ostatnim sortowaniem?

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

Uwaga boczna: Nie obchodzi mnie, że listy są modyfikowane.

Answer 1

Proste rozszerzenie fazy scalania sortowania może to zrobić w czasie O (n lg m) (gdzie n = całkowita liczba pozycji i m = liczba list), przy użyciu priority queue (np. heap). Pseudokod:

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 

i prosty (przetestowane!) Beton implementacja w 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

można spróbować stosowania seryjnej sortowania jedną naraz do każdej z list:

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

Ma to algorytm sortowania korespondencji seryjnej. Zasadniczo przejdziesz do listy 1 i 2 i scalisz je. Następnie możesz wziąć tę nową połączoną listę i posortować ją według listy 3, a to będzie trwało, dopóki nie masz jednej w pełni posortowanej listy.

EDIT:

Faktycznie, ponieważ twoje listy są już klasyfikowane, tylko ostatnia część rodzaju scalania byłaby potrzebna. Mogłabym iteracyjnie łączyć listy w coraz większe części, jednocześnie sortując każdą z tych większych list, aż do uzyskania pełnej listy, która jest w zasadzie tym, co sortowanie scalone wykonuje po zakończeniu dzielenia i podbijania.

Answer 3

Jeżeli wydajność nie jest problemem, chciałbym uporządkować ostatni list. Kod jest bardziej czytelny, krótszy i mniej podatny na zepsucie przez kogoś, kto wróci do kodu w przyszłości.

Answer 4

Jest to standardowy (choć w 8 sposób) scalanie.

Zasadniczo "otwarte" ośmiu posortowanych list następnie rozpocząć ich przetwarzanie, wydobywania najniższej wartości za każdym razem, coś jak:

# 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

Zasadniczo robisz część multiway mergesort, np CEPT swoje rzeczy jest już posortowana ...

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

Wystarczy znaleźć najniższe w każdej tablicy (prawie wykorzystywać jako stosy) i umieścić, że w produkcji aż wszystkie stosy są puste ...

Answer 6

Ty chcesz a merge sort. Twoje listy są już podzielone, ale nie aż do najmniejszego poziomu.Możesz to zrobić:

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

To nie powinno być/działanie pamięci czasochłonne, ponieważ powiązanie należy dodać link z ostatniego węzła w na liście do pierwszego elementu następnej listy.