Les deux techniques de tri, tri rapide et fusion, reposent sur la méthode diviser pour régner dans laquelle l’ensemble des éléments est séparé, puis combiné après réarrangement. Le tri rapide nécessite généralement plus de comparaisons que le tri par fusion pour le tri d'un grand ensemble d'éléments.
Tableau de comparaison
| Base de comparaison | Tri rapide | Tri par fusion |
|---|---|---|
| Partitionnement des éléments du tableau | La division d'une liste d'éléments n'est pas nécessairement divisée en deux. | Le tableau est toujours divisé en deux (n / 2). |
| Pire complexité de cas | O (n2) | O (n log n) |
| Fonctionne bien sur | Plus petit tableau | Fonctionne bien dans tout type de tableau. |
| La vitesse | Plus rapide que les autres algorithmes de tri pour les petits ensembles de données. | Vitesse constante dans tous les types de jeux de données. |
| Espace de stockage supplémentaire requis | Moins | Plus |
| Efficacité | Inefficace pour les grands tableaux. | Plus efficace. |
| Méthode de tri | Interne | Externe |
Définition du tri rapide
Le tri rapide est un algorithme de tri très répandu, car il est rapide pour les matrices courtes. L'ensemble des éléments est divisé en parties à plusieurs reprises jusqu'à ce qu'il ne soit plus possible de le diviser davantage. Le tri rapide est également appelé tri par échange de partition . Il utilise un élément clé (appelé pivot) pour partitionner les éléments. Une partition contient les éléments plus petits que l'élément clé. Une autre partition contient les éléments supérieurs à l'élément clé. Les éléments sont triés de manière récursive.
Supposons que A soit un tableau A [1], A [2], A [3], …… .., A [n] de n nombres qui doivent être triés. L'algorithme de tri rapide comprend les étapes suivantes.
- Le premier élément ou tout élément aléatoire sélectionné comme clé, supposons clé = A (1).
- Le pointeur «bas» est placé au deuxième et le pointeur «haut» au dernier élément du tableau, c'est-à-dire bas = 2 et haut = n;
- Incrémentez constamment le pointeur «bas» d’une position jusqu’à la touche (A [bas]>).
- Constamment, décrémentez le pointeur «haut» d’une position jusqu’à (touche [[]] <=).
- Si up est supérieur à low, échange A [low] avec A [up].
- Répétez les étapes 3, 4 et 5 jusqu'à ce que la condition de l'étape 5 échoue (c.-à-d. Up <= low), puis échangez A [up] avec la clé.
- Si les éléments à gauche de la clé sont plus petits que la clé et que les éléments à droite de la clé sont plus grands que la clé, le tableau est partitionné en deux sous-tableaux.
- La procédure ci-dessus est appliquée à plusieurs reprises aux sous-matrices jusqu'à ce que tout le tableau soit trié.
Avantages et inconvénients
Il possède un bon comportement de cas moyen. La complexité du tri rapide est complexe, car elle est plus rapide que des algorithmes tels que le tri à bulle, le tri par insertion et le tri par sélection. Cependant, il est complexe et très récursif, c’est la raison pour laquelle il n’est pas adapté aux grands tableaux.
Définition du tri par fusion
Le tri par fusion est un algorithme externe qui repose également sur une stratégie de division et de conquête. Les éléments sont divisés en sous-tableaux (n / 2) encore et encore jusqu'à ce qu'il ne reste qu'un seul élément, ce qui réduit considérablement le temps de tri. Il utilise un stockage supplémentaire pour stocker le tableau auxiliaire. Le tri par fusion utilise trois tableaux, deux étant utilisés pour stocker chaque moitié et le troisième pour stocker la liste triée finale. Chaque tableau est ensuite trié de manière récursive. Enfin, les sous-tableaux sont fusionnés pour en faire la taille n des éléments du tableau. La liste est toujours divisée en seulement la moitié (n / 2) différente de la tri rapide.
Soit A le tableau de n nombre d’éléments à trier A [1], A [2], ………, A [n]. Le tri par fusion suit les étapes indiquées.
- Divisez le tableau A en approximativement n / 2 sous-tableau trié par 2, ce qui signifie que les éléments des groupes (A [1], A [2]), (A [3], A [4]), (A [ k], les sous-tableaux A [k + 1]), (A [n-1], A [n]) doivent être triés.
- Combinez chaque paire de paires pour obtenir la liste des sous-matrices triées de taille 4; les éléments des sous-réseaux sont également classés dans l'ordre (A [1], A [2], A [3], A [4]), ……, (A [k-1], A [k], A [k + 1], A [k + 2]), ……., (A [n-3], A [n-2], A [n-1], A [n]).
- L'étape 2 est exécutée de manière répétée jusqu'à ce qu'il n'y ait qu'un seul tableau trié de taille n.
Avantages et inconvénients
L'algorithme de tri par fusion fonctionne exactement de la même manière et avec précision, quel que soit le nombre d'éléments impliqués dans le tri. Cela fonctionne bien même avec le grand ensemble de données. Cependant, il consomme une plus grande partie de la mémoire.
Principales différences entre le tri rapide et le tri par fusion
- Dans le tri par fusion, le tableau doit être divisé en deux moitiés seulement (c'est-à-dire n / 2). Par contre, en tri rapide, il n’ya aucune contrainte de diviser la liste en éléments égaux.
- Le cas le plus complexe du tri rapide est O (n2), car il nécessite beaucoup plus de comparaisons dans les pires conditions. En revanche, le tri par fusion présente les mêmes cas extrêmes et la même complexité, à savoir O (n log n).
- Le tri par fusion peut fonctionner avec n'importe quel type d'ensembles de données, grands ou petits. Au contraire, le tri rapide ne peut pas fonctionner correctement avec des jeux de données volumineux.
- Le tri rapide est plus rapide que le tri par fusion dans certains cas, par exemple pour de petits ensembles de données.
- Le tri par fusion nécessite un espace mémoire supplémentaire pour stocker les tableaux auxiliaires. D'autre part, le tri rapide ne nécessite pas beaucoup d'espace pour un stockage supplémentaire.
- Le tri par fusion est plus efficace que le tri rapide.
- Le tri rapide est une méthode de tri interne dans laquelle les données à trier sont ajustées en même temps dans la mémoire principale. Inversement, le tri par fusion est une méthode de tri externe dans laquelle les données à trier ne peuvent pas être hébergées dans la mémoire en même temps et certaines doivent être conservées dans la mémoire auxiliaire.
Conclusion
Le tri rapide consiste en des cas plus rapides, mais est inefficace dans certaines situations et effectue également de nombreuses comparaisons par rapport au tri par fusion. Bien que le tri par fusion nécessite moins de comparaison, il nécessite un espace mémoire supplémentaire de 0 (n) pour stocker le tableau supplémentaire, tandis qu'un tri rapide nécessite un espace de O (log n).
