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 .
- Qu'est-ce que le tri par fusion en Java?
- Fonctionnement du tri par fusion
- Exemple: diagramme
- la mise en oeuvre
- Complexité
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
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.