Algorithme de fusion - Merge algorithm

Les algorithmes de fusion sont une famille d' algorithmes qui prennent plusieurs listes triées en entrée et produisent une seule liste en sortie, contenant tous les éléments des listes d'entrées dans l'ordre trié. Ces algorithmes sont utilisés comme sous-programmes dans divers algorithmes de tri , le plus connu étant le tri par fusion .

Application

Un exemple de tri par fusion

L'algorithme de fusion joue un rôle essentiel dans l' algorithme de tri par fusion , un algorithme de tri basé sur la comparaison . Conceptuellement, l'algorithme de tri par fusion se compose de deux étapes :

  1. Divisez récursivement la liste en sous-listes de longueur (à peu près) égale, jusqu'à ce que chaque sous-liste contienne un seul élément, ou dans le cas d'un tri par fusion itérative (de bas en haut), considérez une liste de n éléments comme n sous-listes de taille 1. A liste contenant un seul élément est, par définition, triée.
  2. Fusionnez à plusieurs reprises les sous-listes pour créer une nouvelle sous-liste triée jusqu'à ce que la liste unique contienne tous les éléments. La liste unique est la liste triée.

L'algorithme de fusion est utilisé à plusieurs reprises dans l'algorithme de tri par fusion.

Un exemple de tri par fusion est donné dans l'illustration. Il commence par un tableau non trié de 7 entiers. Le tableau est divisé en 7 partitions ; chaque partition contient 1 élément et est triée. Les partitions triées sont ensuite fusionnées pour produire des partitions triées plus grandes, jusqu'à ce qu'il reste 1 partition, le tableau trié.

Fusion de deux listes

La fusion de deux listes triées en une seule peut se faire en temps linéaire et en espace linéaire ou constant (selon le modèle d'accès aux données). Le pseudocode suivant illustre un algorithme qui fusionne les listes d'entrée (soit des listes chaînées, soit des tableaux ) A et B dans une nouvelle liste C . La fonction head renvoie le premier élément d'une liste ; "supprimer" un élément signifie le retirer de sa liste, généralement en incrémentant un pointeur ou un index.

algorithm merge(A, B) is
    inputs A, B : list
    returns list

    C := new empty list
    while A is not empty and B is not empty do
        if head(A) ≤ head(B) then
            append head(A) to C
            drop the head of A
        else
            append head(B) to C
            drop the head of B

    // By now, either A or B is empty. It remains to empty the other input list.
    while A is not empty do
        append head(A) to C
        drop the head of A
    while B is not empty do
        append head(B) to C
        drop the head of B

    return C

Lorsque les entrées sont des listes chaînées, cet algorithme peut être implémenté pour n'utiliser qu'une quantité constante d'espace de travail ; les pointeurs dans les nœuds des listes peuvent être réutilisés pour la comptabilité et pour construire la liste fusionnée finale.

Dans l'algorithme de tri par fusion, ce sous - programme est généralement utilisé pour fusionner deux sous-tableaux A[lo..mid] , A[mid+1..hi] d'un seul tableau A . Cela peut être fait en copiant les sous-tableaux dans un tableau temporaire, puis en appliquant l'algorithme de fusion ci-dessus. L'allocation d'un tableau temporaire peut être évitée, mais au détriment de la rapidité et de la facilité de programmation. Divers algorithmes de fusion sur place ont été conçus, sacrifiant parfois la limite de temps linéaire pour produire un algorithme O ( n log n ) ; voir Fusionner le tri § Variantes pour discussion.

Fusion K-way

La fusion à k voies généralise la fusion binaire à un nombre arbitraire k de listes d'entrée triées. Les applications de la fusion à k voies surviennent dans divers algorithmes de tri, y compris le tri de patience et un algorithme de tri externe qui divise son entrée en k = 1/M− 1 blocs qui tiennent en mémoire, les trie un par un, puis fusionne ces blocs.

Plusieurs solutions à ce problème existent. Une solution naïve consiste à faire une boucle sur les k listes pour sélectionner l'élément minimum à chaque fois, et à répéter cette boucle jusqu'à ce que toutes les listes soient vides :

  • Entrée : une liste de k listes.
  • Bien que l'une des listes ne soit pas vide :
    • Parcourez les listes pour trouver celle avec le premier élément minimum.
    • Affiche l'élément minimum et supprime-le de sa liste.

Dans le pire des cas , cet algorithme effectue ( k −1)( nk/2) des comparaisons d'éléments pour effectuer son travail s'il y a un total de n éléments dans les listes. Il peut être amélioré en stockant les listes dans une file d'attente prioritaire ( min-heap ) codée par leur premier élément :

  • Construisez un min-heap h des k listes, en utilisant le premier élément comme clé.
  • Bien que l'une des listes ne soit pas vide :
    • Soit i = find-min( h ) .
    • Sortez le premier élément de la liste i et supprimez-le de sa liste.
    • Ré-empiler h .

La recherche du prochain plus petit élément à sortir (find-min) et la restauration de l'ordre du tas peuvent désormais être effectuées en un temps O (log k ) (plus précisément, 2⌊log k comparaisons), et le problème complet peut être résolu en O ( n log k ) temps (environ 2 n ⌊log k comparaisons).

Un troisième algorithme pour le problème est une solution de division pour régner qui s'appuie sur l'algorithme de fusion binaire :

  • Si k = 1 , affiche la liste d'entrée unique.
  • Si k = 2 , effectuez une fusion binaire.
  • Sinon, fusionner récursivement les premières listes ⌊ k /2⌋ et les listes k /2⌉ finales , puis les fusionner binairement .

Lorsque les listes d'entrée de cet algorithme sont classées par longueur, la plus courte en premier, cela nécessite moins de n log k comparaisons, c'est-à-dire moins de la moitié du nombre utilisé par l'algorithme basé sur le tas ; en pratique, il peut être à peu près aussi rapide ou lent que l'algorithme basé sur le tas.

Fusion parallèle

Une version parallèle de l'algorithme de fusion binaire peut servir de bloc de construction d'un tri par fusion parallèle . Le pseudocode suivant démontre cet algorithme dans un style parallèle diviser pour régner (adapté de Cormen et al. ). Il opère sur deux tableaux triés A et B et écrit la sortie triée dans le tableau C . La notation A[i...j] désigne la partie de A de l'indice i à j , exclusif.

algorithm merge(A[i...j], B[k...ℓ], C[p...q]) is
    inputs A, B, C : array
           i, j, k, ℓ, p, q : indices

    let m = j - i,
        n = ℓ - k

    if m < n then
        swap A and B  // ensure that A is the larger array: i, j still belong to A; k, ℓ to B
        swap m and n

    if m ≤ 0 then
        return  // base case, nothing to merge

    let r = ⌊(i + j)/2⌋
    let s = binary-search(A[r], B[k...ℓ])
    let t = p + (r - i) + (s - k)
    C[t] = A[r]

    in parallel do
        merge(A[i...r], B[k...s], C[p...t])
        merge(A[r+1...j], B[s...ℓ], C[t+1...q])

L'algorithme fonctionne en divisant A ou B , selon le plus grand, en moitiés (presque) égales. Il divise ensuite l'autre tableau en une partie avec des valeurs inférieures au milieu du premier et une partie avec des valeurs plus grandes ou égales. (La recherche binaire retourne sous - programme l'indice BA [ r ] serait, si elle était en B , que ce toujours un nombre compris entre k et .) Enfin, chaque paire de moitiés est fusionnée récursive , et que les appels récursifs sont indépendants les uns des autres, ils peuvent être réalisés en parallèle. L'approche hybride, où l'algorithme en série est utilisé pour le cas de base de récursivité, s'est avérée performante dans la pratique

Le travail effectué par l'algorithme pour deux tableaux contenant un total de n éléments, c'est-à-dire le temps d'exécution d'une version série de celui-ci, est O ( n ) . Ceci est optimal car n éléments doivent être copiés dans C . Pour calculer l' étendue de l'algorithme, il est nécessaire de dériver une relation de récurrence . Étant donné que les deux appels récursifs de fusion sont en parallèle, seul le plus coûteux des deux appels doit être considéré. Dans le pire des cas, le nombre maximum d'éléments dans l'un des appels récursifs est au plus puisque le tableau avec plus d'éléments est parfaitement divisé en deux. En ajoutant le coût de la Recherche Binaire, on obtient cette récurrence comme borne supérieure :

La solution est , ce qui signifie que cela prend autant de temps sur une machine idéale avec un nombre illimité de processeurs.

Remarque : La routine n'est pas stable : si des éléments égaux sont séparés en séparant A et B , ils s'entrelacent dans C ; également l'échange de A et B détruira l'ordre, si des éléments égaux sont répartis entre les deux tableaux d'entrée. Par conséquent, lorsqu'il est utilisé pour le tri, cet algorithme produit un tri qui n'est pas stable.

Support linguistique

Certains langages informatiques fournissent un support intégré ou une bibliothèque pour fusionner des collections triées .

C++

Le C ++ « de bibliothèque de modèles standard a la fonction std :: fusion , qui fusionne deux gammes de tri itérateurs et std :: inplace_merge , qui fusionne deux plages consécutives triées en place . De plus, la classe std::list ( liste liée) a sa propre méthode de fusion qui fusionne une autre liste en elle-même. Le type des éléments fusionnés doit prendre en charge l' opérateur inférieur à ( < ), ou il doit être fourni avec un comparateur personnalisé.

C++17 permet différentes politiques d'exécution, à savoir séquentielle, parallèle et parallèle non séquencée.

Python

La bibliothèque standard de Python (depuis la 2.6) a également une fonction de fusion dans le module heapq , qui prend plusieurs itérables triés et les fusionne en un seul itérateur.

Voir également

Les références

Lectures complémentaires

Liens externes