Qu’est-ce que le tri par fusion ?
Le tri par fusion est l'algorithme le plus courant pour trier les données en utilisant la technique « diviser pour mieux régner ». Dans cet algorithme, le problème est divisé en sous-problèmes puis, après tri, ils sont fusionnés. Disons que nous avons une liste de nombres non triés, résultat d'un cours sur un certain sujet. Pour les trier par ordre croissant, nous devrons les placer dans une liste allant de bas en haut. Dans cet algorithme de tri par fusion, la liste sera divisée en listes plus petites pour les trier par ordre croissant, puis elle fusionnera les résultats pour une meilleure compréhension. Le tri par fusion en Java peut être expliqué à travers un exemple de tableau {6,9,8,2,4,1}, considérez-le comme le résultat d'un test de classe sur 10. Le tableau (de résultats) sera divisé à plusieurs reprises en morceaux plus petits jusqu'à ce que leur taille soit 1. Ensuite, le processus de fusion a lieu tout en triant les nombres simultanément. Cela nous fournira un résultat allant des notes les plus basses aux notes les plus élevées reçues.
Mise en œuvre
Dans l’implémentation, nous écrirons du code pour l’algorithme de tri par fusion en Java. Les variables requises seront le tableau d'entrée et la longueur du tableau. Ces deux paramètres seront ensuite utilisés pour introduire d'autres paramètres afin de créer la fonction de tri par fusion. Jetons un coup d'œil à l'extrait ci-dessous pour comprendre le fonctionnement général de l'algorithme de tri par fusion en Java.Merge_Sort_Algo (Array, Beginning, End)
/** Three parameters required for the Merge Sort Algorithm
* Array = values of the array
* Beginning = the starting element of the array
* End = the ending element of the array*/
if (Beginning < End) // condition check Beginning must be less than End
set Middle = (Beginning + End) / 2 // Assigning Middle to the array
Merge_Sort_Algo (Array, Beginning, Middle) /** Sorting and merging of elements from Beginning to the Middle */
Merge_Sort_Algo (Array, Middle +1, End) /** Sorting and merging of elements from Middle to the End */
Merge (Array, Beginning, Middle, End) // Merging both the sorted arrays
end of if
End Merge_Sort_Algo
Tout d'abord, via la condition if, le début et la fin sont utilisés pour déterminer le milieu. Puis à l'étape suivante, 2 nouveaux sous-tableaux sont créés en partant du début vers le milieu et l'autre en partant du milieu +1 jusqu'à la fin. Ces tableaux sont divisés jusqu'à ce que leur longueur devienne 1, puis via la fonction de fusion, les sous-tableaux triés Début, Milieu, Milieu + 1 et Fin sont tous fusionnés pour acquérir la solution.
Exemple
Le code suivant en Java explique l'algorithme de tri par fusion :import java.util.Arrays;
class HelloWorld {
public static void merge(
int[] array, int[] new_array_1, int[] new_array_2, int left, int right) {
// defining parameters
int i = 0, j = 0, k = 0;
while (i < left && j < right) { // conditions for merging
if (new_array_1[i] <= new_array_2[j]) {
array[k++] = new_array_1[i++];
}
else {
array[k++] = new_array_2[j++];
}
}
while (i < left) {
array[k++] = new_array_1[i++];
}
while (j < right) {
array[k++] = new_array_2[j++];
}
}
public static void mergeSort(int[] array, int length) { /** required parameters */
if (length < 2) { //condition for the length of array
return;
}
int middle = length / 2; // defining new parameter middle
int [ ] new_array_1 = new int [middle]; /** defining the new first array after division */
int [ ] new_array_2 = new int [length - middle]; /** defining the new second array */
for (int i = 0; i < middle; i++) { /**applying condition for sorting of new array 1 */
new_array_1 [ i ] = array [ i ];
}
for (int i = middle; i < length ; i++) { /**applying condition for sorting of new array 2 */
new_array_2 [ i - middle] = array [ i ];
}
mergeSort (new_array_1, middle); /** calling merge sort function for new array 1 */
mergeSort (new_array_2, length - middle); /** calling merge sort function for new array 2 */
merge(array, new_array_1, new_array_2, middle, length - middle); /** calling function for merging of new array 1 and new array 2 */
}
public static void main(String[] args) {
int [ ] testScores = {6,9,8,2,4,1};
int size = testScores.length;
System.out.println("Original Array " + Arrays.toString(testScores) + "\n");
mergeSort(testScores, size);
System.out.println("After Merge Sort " + Arrays.toString(testScores) + "\n");
}
}
Sortir
Tableau d'origine [6, 9, 8, 2, 4, 1] Après tri par fusion [1, 2, 4, 6, 8, 9]
GO TO FULL VERSION