Programme de tri par fusion en Java : différence entre le tri par fusion et le tri rapide

Publié: 2021-05-25

Table des matières

Introduction au programme Merge Sort en JAVA

Comme son nom l'indique, le programme de tri par fusion en JAVA est un algorithme de tri. Il a été classiquement conceptualisé comme l'algorithme diviser pour régner en JAVA. Le programme de tri par fusion en Java fonctionne en décomposant de manière récursive un tableau d'entrée en deux ou plusieurs de ses sous-problèmes constitutifs jusqu'à ce qu'ils soient suffisamment simples pour être résolus directement.

Les sous-problèmes constitutifs peuvent être similaires ou quelque peu liés au problème parent. Les solutions individuelles à chaque sous-problème sont ensuite combinées pour atteindre la solution au problème parent d'origine.

Comment fonctionne le programme Merge Sort en Java ?

Comme indiqué précédemment, le programme de tri par fusion dans JAVA est un algorithme de division pour régner. Il s'agit d'un tri stable, ce qui signifie que les éléments du tableau conservent leurs positions d'origine les uns par rapport aux autres tout au long du processus de tri.

Diviser: Dans cette étape, un tableau d'entrée est divisé en ses deux moitiés constitutives. Cette étape est continuellement répétée pour tous les demi-réseaux résultants jusqu'à ce qu'il n'y ait plus de demi-réseaux à diviser davantage.
Conquérir : dans cette étape, les tableaux divisés sont triés et fusionnés de bas en haut pour atteindre le tableau trié final.

Différence entre le programme Quicksort et Merge Sort en Java

Bien que fonctionnellement similaire, un accent pertinent doit être mis sur la différence fondamentale entre le tri rapide et le tri fusionné en JAVA.

Mécanisme : Quicksort est un algorithme de tri interne, sur place, tandis que mergesort est un algorithme de tri externe, hors place. Dans le tri rapide, les éléments sont triés sur la base d'un élément clé appelé pivot. Le pivot est généralement la valeur médiane dans un tableau d'entrée. Les éléments avec une valeur inférieure au pivot sont poussés vers le côté gauche du pivot, tandis que les éléments avec une valeur supérieure vers le côté droit du pivot. Ici, le côté gauche est appelé partition gauche et le côté droit est appelé partition droite. Au contraire, mergesort divise un tableau en deux sous-tableaux (n/2) à plusieurs reprises jusqu'à ce qu'il ne reste qu'un seul élément. Il combine ensuite les sous-tableaux pour former le tableau trié.
Application : Alors que le tri rapide convient aux petits tableaux, le tri par fusion fonctionne avec n'importe quel tableau, quelle que soit sa taille.
Vitesse : Dans le cas du tri rapide, plus le jeu de données est petit, plus l'algorithme est rapide. Mergesort, en revanche, fonctionne à une vitesse constante pour tous les ensembles de données.
Espace requis et utilisation de la mémoire : comme mentionné précédemment, le tri par fusion est un algorithme de tri externe et déplacé. Sa complexité spatiale est O (n). Par conséquent, il nécessite un stockage supplémentaire de (O (n)) pour trier le tableau auxiliaire.

Lisez aussi: Types de littéraux en Java avec des exemples

Analyse de la complexité temporelle du programme Merge Sort en JAVA

Le programme de tri par fusion en JAVA a une complexité temporelle de O (n*log n). Selon la recherche binaire, chaque fois qu'un nombre est divisé en deux à chaque étape, il peut être représenté par la fonction logarithmique 'log n'. Le nombre d'étapes (au plus) peut être représenté par log n +1. Le milieu de tout sous-tableau est O (1).

Ainsi, pour fusionner les sous-réseaux, un temps d'exécution de O(n) sera nécessaire. Par conséquent, le temps total pour le programme de tri par fusion dans JAVA devient n (log n +1). Cela équivaut à une complexité temporelle de O (n * log n) dans les trois cas (pire, moyen et meilleur) car le tri par fusion prend toujours un temps linéaire pour fusionner deux moitiés.

Apprenez des cours de logiciels en ligne dans les meilleures universités du monde. Gagnez des programmes Executive PG, des programmes de certificat avancés ou des programmes de maîtrise pour accélérer votre carrière.

Résumé

Tout comme les données triées pour les humains sont logiquement solides et plus faciles à comprendre, les tableaux triés sont plus faciles à gérer pour les ordinateurs. C'est là que le programme de tri par fusion en JAVA s'avère avantageux. Il s'agit d'un algorithme de tri efficace, polyvalent et basé sur la comparaison.

Si vous souhaitez en savoir plus sur Java, le développement de logiciels à pile complète, consultez le programme Executive PG de upGrad & IIIT-B en développement de logiciels à pile complète, conçu pour les professionnels en activité et offrant plus de 500 heures de formation rigoureuse, 9+ projets et affectations, statut d'ancien de l'IIIT-B, projets de synthèse pratiques et aide à l'emploi avec les meilleures entreprises.

Qu'est-ce que le tri en programmation ?

Le tri est la technique consistant à placer des objets dans un ordre particulier. Cela est généralement fait pour les rendre plus faciles à gérer ou pour en faciliter l'accès. En informatique, nous avons des algorithmes de tri pour les structures de données. Ces algorithmes de tri peuvent être divisés en deux catégories. L'un est les algorithmes de tri basés sur la comparaison et l'autre est les algorithmes de tri basés sur l'insertion. Dans les algorithmes de tri basés sur la comparaison, un élément est comparé à un autre élément pour trouver la clé de tri correspondante, qui est la seule clé commune entre eux. Dans les algorithmes de tri basés sur l'insertion, le nouvel élément est ajouté au début d'un tableau et l'élément placé à la fin est décalé au début.

Quels sont les types d'algorithmes de tri en programmation ?

Les algorithmes de tri sont principalement classés en 3 types : tri séquentiel, tri parallèle, tri partitionné. Le tri séquentiel est le plus facile à comprendre. C'est celui que nous utilisons lorsque nous trions dans notre tête. Tout est trié du plus petit au plus grand. Les algorithmes de tri séquentiel les plus courants sont le tri par insertion, le tri à bulles, le tri rapide et le tri par fusion. Tous ces algorithmes de tri peuvent être facilement parallélisés. Dans le cas d'un tri parallèle, chacune des tâches dépend du résultat de la tâche précédente. Ainsi, l'ordre de sortie n'est pas garanti. Deux algorithmes de tri parallèles utilisés sont le tri topologique et le tri par fusion ascendant. Les algorithmes de tri de partitionnement tentent de partitionner le tableau d'entrée afin que chaque sous-tableau puisse être trié individuellement. Les algorithmes de tri de partitionnement incluent la recherche binaire, le chaînage, le tri par tas et le tri par base.

Quelles sont les différences entre le tri par fusion et le tri rapide ?

Le tri par fusion est un algorithme de division pour régner. Il divise une liste en deux partitions en fonction d'un élément pivot, trie de manière récursive chacune des partitions, puis fusionne la sortie. L'étape de fusion peut être effectuée avec un tri de fusion parallèle. Le tri rapide est un algorithme de tri O(nlogn). C'est un algorithme beaucoup plus simple, mais il doit pivoter sur un élément de tableau aléatoire à chaque fois.