Différence entre le tri rapide et le tri par fusion

Le tri des éléments dans une liste est une tâche banale et prenant souvent beaucoup de temps. Le terme tri désigne généralement l'agencement des éléments d'une liste par ordre croissant ou décroissant en fonction d'une relation de commande prédéfinie. Le tri est souvent destiné à la recherche, ce qui constitue une autre activité fondamentale dans le traitement des données. Imaginez à quel point il aurait été difficile de rechercher un mot dans un dictionnaire si les mots qu'il contenait n'avaient pas été organisés ni triés. C'est la raison pour laquelle les entrées d'un dictionnaire sont conservées dans un ordre alphabétique standard. De nombreuses tâches et calculs deviennent sans effort simplement en triant. Et c’est là que viennent les algorithmes de tri.

Un algorithme de tri n'est rien d'autre qu'une méthode pour organiser les éléments d'une liste dans un ordre spécifique, tel que la plus petite valeur, la plus élevée, la plus forte, l'ordre croissant, l'ordre croissant, l'ordre décroissant, l'alphabet, etc. sont numériques et lexicographiques. Les algorithmes utilisent souvent le tri comme sous-programme de clé. Il existe une grande variété d'algorithmes de tri utilisés, chacun utilisant un riche ensemble de techniques. Un algorithme aussi populaire mais tout aussi puissant est l’algorithme Divide and Conquer, qui est un algorithme basé sur une récursion à plusieurs branches. Quick Sort et Merge Sort sont les deux algorithmes couramment utilisés basés sur les algorithmes Divide and Conquer..

Quel est le tri rapide?

Quick Sort est un algorithme de tri hautement efficace basé sur l'approche diviser pour régner, qui est assez similaire à l'approche dynamique dans laquelle un problème est divisé en deux sous-problèmes ou plus, puis résolu de manière récursive. Si la taille des sous-problèmes est suffisamment petite, ils sont résolus simplement de manière simple et sans tracas. Également appelé tri par échange de partitions, l'algorithme de tri rapide divise la liste à trier en trois parties principales: 1) élément pivot (éléments centraux), 2) éléments inférieurs au pivot et 3) éléments supérieurs au pivot. Le pivot lui-même est déplacé entre les deux groupes jusqu'à sa position finale et QUICK SORT est ensuite appliqué de manière récursive..

Quel est le tri par fusion?

Le tri par fusion est un autre algorithme de tri à usage général basé sur la technique de division et de conquête. C’est l’un des algorithmes de tri les plus respectés et les plus populaires, conçu pour être utilisé efficacement pour trier les données stockées de manière externe dans un fichier. Il offre un comportement O (n log n) dans le pire des cas tout en utilisant un stockage supplémentaire O (n). Il divise une collection 'A' en deux collections plus petites, qui sont ensuite triées. Dans la phase finale, ces deux collections triées sont fusionnées en une seule collection de taille n. Ce sera la liste triée. L'algorithme est assez rapide et est également un type stable, et est idéalement préféré pour les listes chaînées.

Différence entre le tri rapide et le tri par fusion

Les bases

- Le tri rapide et le tri par fusion sont les algorithmes de tri basés sur la division et la conquête avec le même principe de base: diviser un problème en deux sous-problèmes ou plus, puis les résoudre de manière récursive. Cependant, ils diffèrent par les procédures de fusion et en termes de performances. Le tri rapide est généralement meilleur et plus rapide que d’autres algorithmes de tri, y compris le tri par fusion pour les petits ensembles de données, tandis que le tri par fusion maintient la cohérence quel que soit le type d’ensembles de données. Le tri rapide est idéal pour les tableaux, tandis que le tri par fusion est idéal pour les listes chaînées..

La complexité de l'espace

- Le tri dans l'algorithme de tri rapide est effectué de manière récursive et chaque appel récursif requiert un emplacement de pile. Il ne nécessite pas d'espace supplémentaire pour la fusion, à l'exception d'un seul espace mémoire pour la fusion. Comme il s'agit d'un algorithme de tri sur place, aucun espace supplémentaire n'est requis pour effectuer le tri. En fait, il utilise le même tableau lors de la division et de la fusion du tableau. En revanche, dans le tri par fusion, il existe plusieurs façons de représenter des données dans un fichier ou sous forme de tableau. Elle nécessite donc des zones de travail telles que des sous-fichiers ou des tableaux de même taille nécessitant de l'espace supplémentaire..

Pire Complexité

- Le pire cas de tri rapide se produit lorsque le partitionnement est déséquilibré, ce qui dépend des éléments utilisés pour le partitionnement. Dans ce cas, l'algorithme s'exécute de manière asymptotique aussi lentement que le tri par insertion. La pire performance du tri rapide est O (n²) et est laissé comme un exercice. Cependant, il est possible d’éviter cela en choisissant le bon pivot. Le pire cas de tri par fusion, en revanche, se produit lorsque le nombre maximal de comparaisons doit être effectué. Compte tenu des performances linéaires lors de la fusion, la performance la plus défavorable du tri par fusion est O (n log₂ n).

Performance

- Bien que les algorithmes de tri rapide et de tri de fusion soient basés sur l'approche du tri par division et conquête, ils diffèrent par les méthodes utilisées pour effectuer les procédures de fractionnement et de fusion. Pour le tri rapide, le gros du travail consiste à partitionner la liste en deux sous-listes avant que celles-ci soient triées. Pour le tri par fusion, le gros du travail consiste à fusionner deux sous-listes après que les sous-listes ont été triées. Le tri par fusion nécessite un tableau temporaire pour la fusion de deux sous-tableaux, alors qu'aucun espace de tableau supplémentaire n'est requis pour le tri rapide, ce qui le rend plus économe en espace que le tri par séparation..

Tri rapide et tri par fusion: Tableau de comparaison

Résumé du tri rapide et du tri par fusion

Les algorithmes de tri rapide et de tri de fusion sont tous deux basés sur l'approche du tri par division et conquête. Cependant, ils diffèrent par les méthodes utilisées pour effectuer les procédures de scission et de fusion. Ils travaillent essentiellement sur le même principe - diviser un problème en deux sous-problèmes ou plus, puis les résoudre de manière récursive. Le tri par fusion est plus efficace que le tri rapide dans le pire des cas, mais les deux sont également efficaces dans le cas moyen. Mais le tri rapide est plus efficace en termes d'espace que le tri par fusion. Donc, le tri rapide est sans aucun doute plus rapide et meilleur que le tri par fusion, mais il devient inefficace dans certaines situations, notamment lorsqu'il s'agit de comparer.