La fusion trie le travail selon ce principe:

1. Les sous-réseaux ordonnés sont recherchés (en option - sont formés).
2. Les sous-réseaux ordonnés sont concaténés en un sous-réseau ordonné commun.

En soi, tout sous-tableau ordonné à l'intérieur du tableau n'a pas beaucoup de valeur. Mais si dans un tableau nous trouvons deux sous-réseaux ordonnés, alors c'est une question complètement différente. Le fait est que vous pouvez les fusionner très rapidement et à moindre coût - pour former un sous-tableau ordonné général à partir d'une paire de sous-réseaux ordonnés.



Comme vous pouvez le voir, la combinaison de deux tableaux ordonnés en un n'est pas facile, mais très simple. Vous devez vous déplacer simultanément dans les deux tableaux de gauche à droite et comparer les paires d'éléments suivantes des deux tableaux. Le plus petit élément est envoyé à la chaudière commune. Lorsque les éléments se terminent dans l'un des tableaux, les éléments restants de l'autre tableau sont simplement transférés dans la liste principale dans l'ordre.

C'est le sel des algorithmes de cette classe. Initialement, un tableau aléatoire peut être divisé en plusieurs petits sous-réseaux ordonnés. Dans la fusion par paire, le nombre de sous-réseaux ordonnés diminue, la longueur de chacun d'eux augmente. À la dernière étape, le tableau se compose de seulement deux sous-réseaux ordonnés qui fusionnent en une seule structure ordonnée.


L'auteur de ce concept est John von Neumann. Parfois, il y a une affirmation controversée selon laquelle il a trouvé le tri lors du travail sur le projet de Manhattan, car il était confronté à la tâche de fournir des calculs efficaces d'une énorme quantité de données statistiques dans le développement d'une bombe nucléaire. Il est difficile d'apprécier la plausibilité de cette version, puisque ses premiers travaux sur le tri par fusion remontent à 1948, et la création de la bombe s'était achevée 3 ans plus tôt. Cependant, quel type de tri atomique existe-t-il, examinons-le.

Fusion Neumann naturelle

L'algorithme de Neyman a été influencé par les caractéristiques de conception des ordinateurs des années 40. Cela ressemblait à ceci:

1. Au total, trois bandes magnétiques sont utilisées - la principale, sur laquelle sont enregistrées les données non triées et deux données auxiliaires.
2. Les données sont lues séquentiellement à partir de la bande principale.
3. Bien que les données lues séquentiellement soient un sous-tableau ordonné, elles sont copiées sur l'une des bandes auxiliaires.
4. Dès que le sous-tableau trié suivant est terminé (c'est-à-dire qu'un élément plus petit que le précédent se trouve sur la bande principale), un pointeur est placé sur la bande auxiliaire (fin du sous-tableau) et le passage à une autre bande auxiliaire se produit.
5. Les points 2 à 4 sont répétés à nouveau, seules les données sont transférées sur une autre bande auxiliaire. À la fin du sous-tableau ordonné suivant, la bande principale passe alternativement à une bande auxiliaire, puis à une autre.
6. Lorsque toutes les données de la bande principale ont été lues, le traitement des bandes auxiliaires a lieu.
7. Les deux bandes auxiliaires lisent les données tour à tour.
8. Dans ce cas, les données suivantes de deux bandes sont comparées. Selon les résultats de la comparaison, le plus petit élément de la paire est enregistré sur la bande principale.
9. Étant donné que les limites des tableaux sur les bandes auxiliaires sont marquées de pointeurs, la lecture et la comparaison se produisent uniquement dans les sous-tableaux triés.
10. Si, sur l'une des bandes auxiliaires, les éléments de la sous-matrice suivante sont terminés, à partir de la bande restante, le reste de la sous-matrice est simplement transféré vers la bande principale.
11. Nous répétons tout le processus jusqu'à ce que les données sur la bande principale soient un tableau entièrement ordonné.

Le tri Neumann est un algorithme adaptatif: il fixe non seulement les morceaux triés du tableau, mais essaie tout d'abord de les augmenter, de sorte que sur la base de sous-réseaux ordonnés allongés pour former des sous-réseaux ordonnés plus longs. Par conséquent, il est également appelé tri de fusion adaptatif .

La complexité de cet algorithme est modeste - O ( n ² ), et, néanmoins, pour les pionniers de l'informatique en tube, c'était une percée.

Sur l'exemple de ce premier tri par fusion, un inconvénient de cette classe d'algorithmes est déjà visible - le coût de la mémoire supplémentaire. À cet égard, presque tous les tri de fusion nécessitent en outre O ( n ), cependant, les exceptions élégantes sont rares.

Fusion directe Bowes-Nelson

À proprement parler, l'algorithme de Bowes-Nelson est un réseau de tri, pas de tri. Dans le processus, le tableau et tous ses sous-réseaux sont divisés en deux et rien n'empêche toutes ces moitiés d'être traitées en parallèle à toutes les étapes. Cependant, il peut également être représenté sous forme de tri. Et nous aborderons également le sujet des réseaux de tri.

1. Le tableau est divisé en deux - dans les moitiés gauche et droite.
2. Les éléments sont divisés en groupes.
3. À la première itération, ce sont les deux éléments (le 1er élément de la moitié gauche + le 1er élément de la moitié droite, le 2e élément de la moitié gauche + le 2e élément de la moitié droite, etc.), à la deuxième itération - les quatre éléments (1- 2e et 2e éléments de la moitié gauche + 1er et 2e éléments de la moitié droite, 3e et 4e éléments de la moitié gauche + 3e et 4e éléments de la moitié droite, etc.), sur la troisième - huit, etc.
4. Les éléments de chaque groupe de la moitié gauche sont des sous-réseaux triés, les éléments de chaque groupe de la moitié droite sont également des sous-réseaux triés.
5. Fusionnez les sous-tableaux triés du paragraphe précédent.
6. Nous revenons au point 1. Le cycle continue jusqu'à ce que la taille des groupes soit inférieure à la taille du tableau.

Il peut sembler qu'une mémoire supplémentaire soit requise ici. Mais non! Pour une perception plus compréhensible dans l'animation, les moitiés gauche et droite du tableau sont situées l'une sur l'autre, de sorte que la position relative des sous-réseaux comparés est plus évidente. Cependant, en raison d'une stricte bissection, un algorithme est possible dans lequel toutes les comparaisons et tous les échanges sont effectués, sans impliquer de ressources supplémentaires de la mémoire. Ce qui est très inhabituel pour le tri par fusion.

def bose_nelson(data): m = 1 while m < len(data): j = 0 while j + m < len(data): bose_nelson_merge(j, m, m) j = j + m + m m = m + m return data def bose_nelson_merge(j, r, m): if j + r < len(data): if m == 1: if data[j] > data[j + r]: data[j], data[j + r] = data[j + r], data[j] else: m = m // 2 bose_nelson_merge(j, r, m) if j + r + m < len(data): bose_nelson_merge(j + m, r, m) bose_nelson_merge(j + m, r - m, m) return data 

Il y a quelque chose dans toutes les fusions de tri qui les rend similaires à la bombe à hydrogène. La première division se produit, puis la synthèse.

Les références

Fusionner / Fusionner

Articles de série:

• Application Excel AlgoLab.xlsm
• Exchange Sorts
• Tri d'insertion
• Trier par sélection
• Fusionner les tris
  • Fusion équilibrée de haut en bas et de bas en haut
  • Tri de fusion multiphase
  • Tri de fusion en cascade
  • Tri par fusion oscillante
  • Triés filetés et non miscibles
  • Comparaison de tri par fusion
• Trier par distribution
• Tri hybride

Les deux tris mentionnés dans l'article d'aujourd'hui sont désormais disponibles dans l'application AlgoLab (pour ceux qui étudient les algorithmes à l'aide de cette application Excel, mettez à jour le fichier). Et dans quelques jours, avec la sortie d'une prochaine suite sur les types de fusion, plusieurs autres algorithmes de cette classe seront disponibles.

Il y a une restriction pour le tri de Bowes-Nelson - la taille du tableau doit être une puissance de deux. Si cette condition n'est pas remplie, la macro recadrera le tableau à une taille appropriée.

Cet article a été écrit avec le soutien d'EDISON Software, une société qui écrit des logiciels de reconstruction 3D et développe des équipements de mesure sophistiqués .