Comment effectuer un tri par fusion en Java?



Cet article sur le tri par fusion en Java vous aidera à comprendre comment trier une liste d'éléments à l'aide du tri par fusion à l'aide d'un exemple de programme.

Avez-vous déjà entendu parler du terme «Divide and Conquer»? Cet article est tout particulièrement basé sur cette approche. Tri par fusion est un algorithme «diviser et conquérir» dans lequel nous divisons d'abord le problème en sous-problèmes, puis les fusionnons pour conquérir notre solution. Voici un aperçu complet du concept de tri par fusion en J .

Commençons!





Qu'est-ce que le tri par fusion en Java?

Le tri par fusion est l'un des algorithmes de tri disponible et il suit une approche de division pour conquérir. Un problème est divisé en sous-problèmes et combiné pour arriver à la solution finale!

Maintenant, que se passe-t-il exactement pendant le fonctionnement du tri par fusion? Laissez-nous comprendre en détail.



Fonctionnement du tri par fusion

Il y a deux étapes suivies par le tri de fusion pendant le processus:

  • Diviser: Dans cette étape, le tableau d'entrée est divisé en 2 moitiés, le pivot est le milieu du tableau. Cette étape est effectuée de manière récursive pour tous les demi-tableaux jusqu'à ce qu'il n'y ait plus de demi-tableaux à diviser davantage.
  • Conquérir: Dans cette étape, nous trions et fusionnons les tableaux divisés de bas en haut et atteignons notre tableau trié.

Cette approche vous aide à trier facilement les sous-parties des problèmes en premier et, par conséquent, à trouver la solution.

Permettez-moi de vous montrer une représentation picturale du tri par fusion.



Exemple: diagramme

Tri de fusion - Edureka

Ici, vous avez vu à quoi ressemble un tri par fusion. Le concept principal du tri par fusion est que le tri prend moins de temps. Maintenant, passons à notre partie implémentation!

la mise en oeuvre

package MyPackage public class MergeSort {void merge (int arr [], int beg, int mid, int end) {int l = mid - beg + 1 int r = end - mid int LeftArray [] = new int [l] int RightArray [] = new int [r] for (int i = 0 i

Production:
Tableau trié
un
4
17
22
2. 3
40
Quatre cinq
51
55
90

comment convertir une chaîne en date

Voici à quoi ressemble un code Java représentant un tri par fusion. Passer au segment suivant.

Complexité

La complexité est divisée en deux types: la complexité temporelle et la complexité spatiale. Dans le cas du tri par fusion, les données sont comme indiqué ci-dessous:

Complexité

Meilleur cas

Cas moyen

Pire cas

Complexité temporelle

O (n log n)

O (n log n)

O (n log n)

Complexité spatiale

-

-

Sur)

Sur ce, je conclurai cet article. J'espère que le contenu expliqué ci-dessus a ajouté de la valeur à vos connaissances Java. Nous continuerons d'explorer le monde Java ensemble. Restez à l'écoute!

séquence de fibonacci en c ++

Vérifiez par Edureka, une entreprise d'apprentissage en ligne de confiance avec un réseau de plus de 250 000 apprenants satisfaits répartis dans le monde entier. Le cours de formation et de certification Java J2EE et SOA d'Edureka est conçu pour les étudiants et les professionnels qui souhaitent devenir développeur Java. Le cours est conçu pour vous donner une longueur d'avance dans la programmation Java et vous former aux concepts Java de base et avancés ainsi qu'à divers frameworks Java tels que Hibernate et Spring.

Vous avez une question pour nous? Veuillez le mentionner dans la section commentaires de ce ' Fusionner le tri en Java »Et nous vous répondrons dans les plus brefs délais.