Fusion de 8 listes sortingées en c ++, quel algorithme dois-je utiliser?

J’ai 8 listes sortingées que je dois fusionner en 1 liste sortingée. Je ne connais pas le meilleur moyen de faire ça. Je pensais à ce qui suit:

void merge_lists_inplace(list& l1, const list& l2) { list::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 merge_8_lists(list[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]; } 

Mais serait-il préférable de se préoccuper du dernier sorting?

 list merge_8_lists(list[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]; } 

Note latérale: Peu m’importe que les listes soient modifiées.

Une simple extension de la phase de fusion du type de fusion peut effectuer cette opération en 0 (n lg m) heure (où n = nombre total d’éléments et m = nombre de listes), à l’aide d’une queue prioritaire (par exemple, un segment de mémoire ). Pseudocode:

 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 

Et une simple implémentation concrète (non testée!) En C ++:

 #include  #include  template struct cmp_list { bool operator()(const std::list *a, const std::list *b) const { return a->front() < b->front(); } }; template void merge_sorted_lists(std::list &output, std::list > &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 *, cmp_list > pq; for ( typename std::list >::iterator it = input.begin(); it != input.end(); it++) { if (it->empty()) continue; pq.insert(&*it); } while (!pq.empty()) { std::list *p = *pq.begin(); pq.erase(pq.begin()); output.push_back(p->front()); p->pop_front(); if (!p->empty()) pq.insert(p); } } 

Vous pouvez essayer d’appliquer le sorting par fusion à chacune des listes:

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

Cela a l’algorithme pour le sorting par fusion. Essentiellement, vous devez sélectionner les listes 1 et 2 et les fusionner. Ensuite, vous prenez cette nouvelle liste combinée et sortingez avec la liste 3, et cela continue jusqu’à ce que vous ayez une liste entièrement sortingée.

MODIFIER:

En fait, comme vos listes sont déjà sortingées, seule la dernière partie du sorting par fusion sera nécessaire. Je combinerais de manière itérative les listes en parties de plus en plus grandes tout en sortingant chacune de ces listes plus grosses jusqu’à ce que vous ayez votre liste complète, ce qui correspond essentiellement au type de fusion effectué après son approche de division et de conquête.

Si la performance n’est pas une préoccupation, je sortingerais les listes en dernier. Le code est plus lisible, plus court et moins susceptible d’être bousillé par une personne qui revisite le code à l’avenir.

Il s’agit d’un type de fusion standard (bien que 8 directions).

En gros, vous “ouvrez” les huit listes sortingées, puis commencez à les traiter, en extrayant à chaque fois la valeur la plus basse, quelque chose comme:

 # 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 

Fondamentalement, vous faites partie de la fusion multi-voies, sauf que vos fichiers sont déjà sortingés …

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

Il suffit de trouver le plus bas dans chaque tableau (presque comme des stacks) et de le mettre dans votre sortie jusqu’à ce que toutes les stacks soient vides …

Vous voulez un genre de fusion . Vos listes sont déjà divisées, mais pas jusqu’au plus petit niveau. Vous voudrez peut-être faire ceci:

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

Cela ne devrait pas être une opération gourmande en temps / mémoire car la concaténation devrait append un lien du dernier nœud de la liste au premier élément de la liste suivante.