|
Tri par fusion est un algorithme de tri qui fonctionne en divisant récursivement un tableau en sous-tableaux de plus en plus petits jusqu'à ce que chaque sous-tableau ne contienne qu'un seul élément. Les sous-tableaux sont ensuite fusionnés dans un ordre trié, en commençant par le plus petit sous-tableau et en remontant jusqu'au plus grand sous-tableau.
Voici un exemple du fonctionnement du tri par fusion. Commençons par le tableau suivant :
```
[5, 3, 1, 2, 4]
```
Nous divisons d'abord le tableau en deux sous-tableaux :
```
[5, 3]
[1, 2, 4]
```
Nous trions ensuite récursivement chaque sous-tableau. Le premier sous-tableau est déjà trié, nous n’avons donc rien à faire. Le deuxième sous-tableau peut être trié en le divisant récursivement en deux sous-tableaux supplémentaires, et ainsi de suite.
Une fois les sous-tableaux triés, nous pouvons les fusionner dans un ordre trié. Nous commençons par comparer les premiers éléments de chaque sous-tableau. Le plus petit élément est ajouté au tableau trié et l'autre élément est supprimé. Nous continuons ce processus jusqu'à ce que tous les éléments des deux sous-tableaux aient été ajoutés au tableau trié.
```
[1, 2, 3, 4, 5]
```
La dernière étape consiste à renvoyer le tableau trié.
Le tri par fusion présente de nombreux avantages par rapport aux autres algorithmes de tri. Il est garanti de produire un tableau trié en un temps O(n log n), quel que soit l'ordre initial des éléments du tableau. De plus, le tri par fusion est stable, ce qui signifie que les éléments égaux apparaîtront dans le tableau trié dans le même ordre que celui dans lequel ils sont apparus dans le tableau d'origine.
Voici une explication plus détaillée de l’algorithme de tri par fusion :
1. Divisez le tableau en deux sous-réseaux de longueur approximativement égale.
2. Triez de manière récursive chaque sous-tableau.
3. Fusionnez les deux sous-tableaux triés en un seul tableau trié.
L’étape de fusion est la clé du tri par fusion. Il est important de fusionner les sous-tableaux dans un ordre trié. Cela peut être fait en comparant les premiers éléments de chaque sous-tableau et en ajoutant le plus petit élément au tableau trié. L'autre élément est écarté. Ce processus est répété jusqu'à ce que tous les éléments des deux sous-tableaux aient été ajoutés au tableau trié.
Le tri par fusion est un algorithme de tri puissant qui garantit la production d'un tableau trié en un temps O(n log n). Il est également stable, ce qui le rend adapté au tri de données contenant des éléments égaux.
|
