Fusionner le tri en Java

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. Ce tableau sera divisé en deux tableaux qui contiendront chacun 3 éléments comme indiqué ci-dessous à l' étape 2 et continuera à se diviser jusqu'à ce que l'unité soit atteinte à l'étape 4 . Ensuite, l'algorithme de tri par fusion commence à trier les nombres une étape à la fois ( étape 5 ), puis fusionne les nombres dans un tableau plus grand aux étapes 6 et 7 .

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

Conclusion

Merge Sort en Java est un algorithme simple pour acquérir une liste triée à partir d’une liste de nombres non triés. La méthode de base « diviser pour régner » est appliquée pour accéder au tableau trié à partir d’un tableau non trié.