Programme de tri par fusion en Java

Le programme de tri par fusion en Java est l'un des algorithmes les plus utilisés et les plus efficaces. Le tri par fusion est basé sur la technique diviser pour régner qui consiste à diviser un problème donné en plusieurs sous-problèmes et à résoudre chaque sous-problème indépendamment. Lorsque les sous-problèmes sont résolus, nous combinons leurs résultats pour obtenir la solution finale au problème. L'algorithme de tri par fusion peut être implémenté en utilisant la récursion car il implique de travailler avec des sous-problèmes plutôt qu'avec le problème principal.

Comment fonctionne le tri par fusion ?

Considérons un tableau non trié qui doit être trié à l'aide de l'algorithme de tri par fusion. Voici les étapes à suivre pour trier un tableau avec des valeurs : 18, 8, 4, 13, 10, 12, 7 et 11 :

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

• La première étape consiste à trouver un élément pivot sur la base duquel notre tableau d'entrée sera divisé en sous-tableaux.
• Considérons que l'élément 13 est choisi comme pivot ; par conséquent, le tableau d'origine sera divisé en deux sous-tableaux. Le premier sous-tableau contiendra 18, 8, 4, 13 et le deuxième sous-tableau contiendra les éléments restants 10, 12, 7, 11.
• Les sous-tableaux obtenus à l'étape 2 sont subdivisés comme à l'étape 1, et cela continue.
• Une fois que le tableau principal est divisé en sous-tableaux avec des éléments uniques, nous recommençons à fusionner ces sous-tableaux de telle sorte que les éléments fusionnés soient dans l'ordre trié.
• Voici comment fonctionne réellement la division diviser pour mieux régner :

Programme de tri par fusion en Java

Voici un exemple de code montrant l'implémentation du tri par fusion en Java :

Code :

package com.edubca.sorting;
public class MergeSort {
private int[] array;
private int[] tempMergedArr;
private int length;
public static void main(String a[]){
int[] inputArr = {18, 8, 4, 13, 10, 12, 7, 11};
MergeSort mergeSort = new MergeSort();
mergeSort.sort(inputArr);
for(int i:inputArr){
System.out.print(i + " ");
}
}
public void sort(int inputArr[]) {
this.array = inputArr;
this.length = inputArr.length;
this.tempMergedArr = new int[length];
performMergeSort(0, length - 1);
}
private void performMergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Sort the left side of the array call performMergeSort recursively
performMergeSort(lowerIndex, middle);
// Sort the right side of the array call performMergeSort recursively
performMergeSort(middle + 1, higherIndex);
// Merge subparts using a temporary array
mergeData(lowerIndex, middle, higherIndex);
}
}
private void mergeData (int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergedArr[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergedArr[i] <= tempMergedArr[j]) {
array[k] = tempMergedArr[i];
i++;
} else {
array[k] = tempMergedArr[j];
j++;
}
k++;
}
while (i <= middle) {
array[k] = tempMergedArr[i];
k++;
i++;
}
}
}

Le code ci-dessus produira un tableau trié en sortie.

Sortie :

Quand devrions-nous utiliser le tri par fusion ?

Le tri par fusion peut être utilisé dans les scénarios suivants :

• Lorsque la structure de données à trier ne prend pas en charge l'accès aléatoire, le tri par fusion peut être utile et efficace.
• Lorsqu'un niveau élevé de parallélisme est requis, le tri par fusion peut être utilisé car différents sous-problèmes peuvent être résolus indépendamment à l'aide de plusieurs processus exécutés en parallèle.
• Le tri par fusion est plus rapide lorsque vous travaillez avec des listes chaînées, car les pointeurs peuvent facilement être modifiés lors de la fusion des listes.
• Le tri par fusion peut être considéré comme un tri stable, ce qui signifie que le même élément dans un tableau conserve ses positions d'origine les uns par rapport aux autres. Dans les cas où une grande stabilité est requise, on peut opter pour le tri par fusion. 

Analyse de complexité du tri par fusion

Les points ci-dessous analysent la complexité du tri par fusion :

• Le tri par fusion est un algorithme récursif, et sa complexité temporelle est O(n*log n) dans les trois cas (pire, meilleur et moyen), car le tri par fusion divise le tableau en deux moitiés égales et prend un temps linéaire pour les fusionner. .
• La complexité spatiale du tri par fusion est O (n) car elle fonctionne selon l'approche récursive. Par conséquent, le tri par fusion peut être considéré comme un algorithme rapide, efficace en termes d'espace et de temps.

Comparaison du tri par fusion avec d'autres algorithmes

Les points ci-dessous comparent le tri par fusion avec d'autres algorithmes :

• Le tri par tas a la même complexité temporelle que le tri par fusion, mais il ne nécessite qu'un espace auxiliaire O (1) au lieu du O (n) du tri par fusion. Par conséquent, le tri par tas est plus économe en espace que le tri par fusion.
• Les implémentations de tri rapide surpassent généralement le tri par fusion pour trier les tableaux basés sur la RAM.
• Le tri par fusion surpasse les algorithmes de tri rapide et de tri par tas lorsque vous travaillez avec la liste chaînée, car les pointeurs peuvent facilement être modifiés.

Conclusion-Programme pour le tri par fusion en Java

L'article conclut que le tri par fusion est un concept important à comprendre en matière d'algorithmes.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!