Tri rapide est un algorithme interne basé sur la stratégie diviser pour régner. Dans ce:

• Le tableau d’éléments est divisé en parties à plusieurs reprises jusqu’à ce qu’il ne soit plus possible de le diviser davantage.
• Il est également connu sous le nom tri d'échange de partition .
• Il utilise un élément clé (pivot) pour partitionner les éléments.
• Une partition de gauche contient tous les éléments plus petits que le pivot et une partition de droite contient tous les éléments plus grands que l'élément clé.

Tri par fusion est un algorithme externe basé sur la stratégie diviser pour mieux régner. Dans ce:

pour le bash de boucle

• Les éléments sont divisés en deux sous-tableaux (n/2) encore et encore jusqu'à ce qu'il ne reste qu'un seul élément.
• Le tri par fusion utilise un stockage supplémentaire pour trier le tableau auxiliaire.
• Le tri par fusion utilise trois tableaux dont deux sont utilisés pour stocker chaque moitié, et le troisième externe est utilisé pour stocker la liste triée finale en fusionnant les deux autres et chaque tableau est ensuite trié de manière récursive.
• Enfin, tous les sous-tableaux sont fusionnés pour en faire une taille d'élément « n » du tableau.

Tri rapide ou tri par fusion

Partition des éléments dans le tableau : Dans le tri par fusion, le tableau est divisé en seulement 2 moitiés (c'est-à-dire n/2). alors qu'en cas de tri rapide, le tableau est divisé selon n'importe quel rapport. Il n'y a aucune obligation de diviser le tableau d'éléments en parties égales lors d'un tri rapide. Complexité dans le pire des cas : la complexité dans le pire des cas du tri rapide est O(n^2) car de nombreuses comparaisons sont nécessaires dans les pires conditions. alors que dans le tri par fusion, le pire des cas et le cas moyen ont les mêmes complexités O (n log n). Utilisation avec des ensembles de données : le tri par fusion peut bien fonctionner sur tout type d'ensembles de données, quelle que soit sa taille (grande ou petite). alors que le tri rapide ne peut pas bien fonctionner avec de grands ensembles de données. Exigence d'espace de stockage supplémentaire : le tri par fusion n'est pas en place car il nécessite de l'espace mémoire supplémentaire pour stocker les tableaux auxiliaires. tandis que le tri rapide est en place car il ne nécessite aucun stockage supplémentaire. Efficacité : le tri par fusion est plus efficace et fonctionne plus rapidement que le tri rapide en cas de taille de tableau ou d'ensembles de données plus grands. tandis que le tri rapide est plus efficace et fonctionne plus rapidement que le tri par fusion en cas de taille de tableau ou d'ensembles de données plus petits. Méthode de tri : Le tri rapide est une méthode de tri interne où les données sont triées dans la mémoire principale. alors que 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 et nécessitent une mémoire auxiliaire pour le tri. Stabilité : le tri par fusion est stable car deux éléments de valeur égale apparaissent dans le même ordre dans la sortie triée que dans le tableau non trié d'entrée. alors que le tri rapide est instable dans ce scénario. Mais il peut être rendu stable en modifiant le code. Préféré pour : le tri rapide est préféré pour les tableaux. alors que le tri par fusion est préféré pour les listes chaînées. Localité de référence : le tri rapide présente une bonne localité de cache, ce qui rend le tri rapide plus rapide que le tri par fusion (dans de nombreux cas, comme dans un environnement de mémoire virtuelle).