Quelle est la différence entre le tri rapide et le tri par fusion

le différence principale entre quicksort et le type de fusion est que le quicksort trie les éléments en comparant chaque élément avec un élément appelé pivot tandis que le tri par fusion divise le tableau en deux sous-tableaux encore et encore jusqu'à ce qu'il ne reste qu'un élément..

Le tri est la méthode de classement des données dans un ordre particulier. Lors de la disposition des données, il est possible de considérer l'ordre numérique ou lexicographique. Le tri permet de rechercher et d'accéder aux éléments de données plus rapidement et plus rapidement. Il existe différents algorithmes de tri et le tri rapide et le tri par fusion en sont deux..

Zones clés couvertes

1. Qu'est-ce que Quicksort?
     - Définition, fonctionnalité
2. Quel est le tri par fusion
     - Définition, fonctionnalité
3. Quelle est la différence entre le tri rapide et le tri par fusion
     - Comparaison des différences clés

Mots clés

Algorithme, tableau, tri par fusion, tri rapide

Qu'est-ce que Quicksort?

Quicksort est un algorithme interne qui utilise la «technique de division et de conquête». On l'appelle aussi une sorte d'échange de partition. Il utilise un élément clé appelé pivot pour comparer et partitionner les éléments du tableau. Les éléments dont la valeur est inférieure au pivot vont vers le côté gauche du pivot, tandis que les articles dont la valeur est supérieure au pivot vont vers le côté droit du pivot. La section de gauche est appelée la partition de gauche et la section de droite est appelée la partition de droite..

Figure 1: Tri rapide

Reportez-vous à l'exemple ci-dessous.

36 34 43 11 15 20 28 45 27 32

Considérez 32 comme pivot et considérez 36 et 27. Les conditions 36 < pivot, 27 > les pivots sont faux. Par conséquent, nous pouvons échanger ces deux valeurs. Maintenant la liste est la suivante.

27 34 43 11 15 20 28 45 36 32

Considérons les valeurs 34 et 45. Lorsque vous considérez 34 < pivot, the condition is false. Similarly, 45 > la condition de pivot est vraie. Nous pouvons maintenant passer de 45 à 28. Voyons 34 et 28. < pivot is false and 28 > le pivot est faux. Par conséquent, nous pouvons échanger 34 et 28.

27 28 43 11 15 20 34 45 36 32

Considérez 43 et 20. 43 < pivot is false. 20 > le pivot est faux. Par conséquent, nous pouvons échanger les deux nombres. Maintenant la liste est la suivante.

27 28 20 11 15 43 34 45 36 32

Considérons maintenant les 11 et 15. 11 < pivot is true. We can consider 15. It is less than 32. It is the overlapping point, and we can place 32 as follows.

27 28 20 11 15 32 43 34 45 36 

Maintenant, les chiffres dans le côté gauche du pivot sont plus petits que le pivot et le côté droit du pivot est plus grand que le pivot. Nous pouvons appliquer un tri rapide sur les partitions gauche et droite pour trier toute la liste..

Quel est le tri par fusion

Le type de fusion est un algorithme externe qui utilise la «technique diviser pour régner». Il divise le tableau en deux sections. Il trie chaque tableau et les combine pour former le tableau trié. Le tri par fusion nécessite un stockage supplémentaire pour trier le tableau auxiliaire.

Considérez l'exemple suivant.

Figure 2: Tri par fusion

Nous pouvons diviser le tableau en deux sections. Maintenant, il y a deux tableaux comme suit.

38 27 43 3 9 82 10

Considérez 38 27 43 3. Nous pouvons à nouveau le diviser en deux tableaux. Ils sont 38 27 et 43 3. 38 27 se divisent en 38 et 27 tandis que 43 3 se divise en 43 et 3. Le tri 38 et 27 donne 27 38. Le tri 43 3 donne 3 43. Il est maintenant possible de combiner 27 38 et 3 43 Après les avoir triés, on obtient un tableau de 3 27 38 43. 

De même, considérons 9 82 10. Nous pouvons le diviser à nouveau en deux tableaux. Ils sont 9 82 et 10. 9 82 se divise en 9 et 82. De plus, il y a le numéro 10 dans l'autre tableau. 9 et 82 sont classés en 9 82. Ainsi, ce tableau et ce tableau de valeur 10 combinent et fournissent 9 10 et 82.

Enfin, 3 27 38 43 et 9 10 82 se combinent pour fournir le tableau trié.

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

Définition

Quicksort est un algorithme de tri efficace, servant de méthode systématique pour placer les éléments d'un tableau dans l'ordre. En revanche, le tri par fusion est un algorithme de tri efficace, polyvalent et basé sur la comparaison. C’est donc la différence fondamentale entre le tri rapide et le tri par fusion.

La fonctionnalité

Aboveall, la fonctionnalité est la principale différence entre le tri rapide et le tri par fusion. Quicksort trie les éléments en comparant chaque élément avec le pivot tandis que le tri par fusion divise le tableau en deux sous-tableaux (n / 2) encore et encore jusqu'à ce qu'il ne reste qu'un élément..

Application

De plus, alors que quicksort convient aux petits tableaux, le tri par fusion fonctionne pour tout type de tableau..

La vitesse

Une autre différence entre le tri rapide et le tri par fusion est que le tri rapide fonctionne plus rapidement pour les petits ensembles de données, tandis que le tri par fusion fonctionne à une vitesse constante pour tous les ensembles de données..

Besoin d'espace

En outre, l'espace requis constitue également une différence importante entre le tri rapide et le tri par fusion. Quicksort nécessite un minimum d'espace par rapport au tri par fusion.  

Efficacité

De plus, le tri rapide n'est pas efficace pour les baies de grande taille, mais le tri par fusion est plus efficace que le tri rapide. C'est donc une autre différence entre le tri rapide et le tri par fusion.

Conclusion

En résumé, la principale différence entre le tri rapide et le tri par fusion est que le tri rapide trie les éléments en comparant chaque élément à un élément appelé pivot tandis que le tri par fusion divise le tableau en deux sous-tableaux encore et encore jusqu'à ce qu'il ne reste qu'un élément..

Référence:

1. Algorithme Quicksort | Part 2, Education 4u, 15 mars 2018, disponible ici.
2. Exemple de tri par fusion, Education 4u, 15 mars 2018, disponible ici.

Courtoisie d'image:

1. «Quicksort-diagram» de Znupi - Travail personnel (domaine public) via Commons Wikimedia
2. «Diagramme d’algorithmes de tri de fusion» par Vineet Kumar sur Wikipedia anglais - Transféré de en.wikipedia à Commons par Eric Bauman à l'aide de CommonsHelper (domaine public) via Commons Wikimedia