>
Menu

Merge Sort In Java - Programme pour implémenter MergeSort

  • Principal
  • Autre
  • Merge Sort In Java - Programme pour implémenter MergeSort

merge sort java program implement mergesort

Ce didacticiel explique ce qu'est le tri par fusion en Java, l'algorithme MergeSort, le pseudo code, l'implémentation du tri par fusion, des exemples de tri par fusion itératif et récursif:

La technique de tri par fusion utilise une stratégie «Divide-and-Conquer». Dans cette technique, l'ensemble de données à trier est divisé en unités plus petites pour le trier.

=> Lisez la série de formations Easy Java.

Fusionner le tri en Java

Ce que vous apprendrez:

Fusionner le tri en Java

Par exemple, si un tableau doit être trié en utilisant mergesort, alors le tableau est divisé autour de son élément central en deux sous-tableaux. Ces deux sous-tableaux sont ensuite divisés en unités plus petites jusqu'à ce que nous n'ayons qu'un seul élément par unité.

Une fois la division effectuée, cette technique fusionne ces unités individuelles en comparant chaque élément et en les triant lors de la fusion. De cette façon, au moment où le tableau entier est fusionné, nous obtenons un tableau trié.

Dans ce tutoriel, nous aborderons tous les détails de cette technique de tri en général y compris son algorithme et ses pseudo codes ainsi que l'implémentation de la technique en Java.

Algorithme MergeSort en Java

Voici l'algorithme de la technique.

#1) Déclarer un tableau myArray de longueur N

#deux) Vérifiez si N = 1, myArray est déjà trié

# 3) Si N est supérieur à 1,

  • définir à gauche = 0, à droite = N-1
  • calculer milieu = (gauche + droite) / 2
  • Appelez le sous-programme merge_sort (myArray, left, middle) => ceci trie la première moitié du tableau
  • Appelez le sous-programme merge_sort (myArray, middle + 1, right) => cela triera la seconde moitié du tableau
  • Appelez le sous-programme merge (myArray, left, middle, right) pour fusionner les tableaux triés dans les étapes ci-dessus.

# 4) Sortir

Comme vu dans les étapes de l'algorithme, le tableau est divisé en deux au milieu. Ensuite, nous trions récursivement la moitié gauche du tableau, puis la moitié droite. Une fois que nous avons trié individuellement les deux moitiés, elles sont fusionnées pour obtenir un tableau trié.

Fusionner le pseudo-code de tri

Voyons le pseudo-code de la technique Mergesort. Comme nous l’avons déjà dit, car il s’agit d’une technique de «division et de conquête», nous présenterons les routines permettant de diviser l’ensemble de données, puis de fusionner les ensembles de données triés.

procedure mergesort( var intarray as array ) if ( n == 1 ) return intarray var lArray as array = intarray[0] ... intarray [n/2] var rArray as array = intarray [n/2+1] ... intarray [n] lArray = mergesort(lArray ) rArray = mergesort(rArray ) return merge(lArray, rArray ) end procedure procedure merge( var l_array as array, var r_array as array ) var result as array while (l_array and r_array have elements ) if (l_array [0] > r_array [0] ) add r_array [0] to the end of result remove r_array [0] from r_array else add l_array [0] to the end of result remove l_array [0] from l_array end if end while while (l_array has elements ) add l_array [0] to the end of result remove l_array [0] from l_array end while while (r_array has elements ) add r_array [0] to the end of result remove r_array [0] from r_array end while return result end procedure

Dans le pseudo-code ci-dessus, nous avons deux routines, à savoir Mergesort et merge. La routine Mergesort divise le tableau d'entrée en un tableau individuel assez facile à trier. Ensuite, il appelle la routine de fusion.

La routine de fusion fusionne les sous-tableaux individuels et renvoie un tableau trié résultant. Après avoir vu l'algorithme et le pseudo-code pour le tri par fusion, illustrons maintenant cette technique à l'aide d'un exemple.

Illustration MergeSort

Considérez le tableau suivant qui doit être trié à l'aide de cette technique.

Illustration de tri de fusion

Maintenant, selon l'algorithme de tri Merge, nous allons diviser ce tableau à son élément central en deux sous-tableaux. Ensuite, nous continuerons à diviser les sous-tableaux en tableaux plus petits jusqu'à ce que nous obtenions un seul élément dans chaque tableau.

Une fois que chaque sous-tableau ne contient qu'un seul élément, nous fusionnons les éléments. Lors de la fusion, nous comparons les éléments et nous nous assurons qu'ils sont en ordre dans le tableau fusionné. Nous progressons donc pour obtenir un tableau fusionné qui est trié.

Le processus est illustré ci-dessous:

Processus de tri de fusion

Comme le montre l'illustration ci-dessus, nous voyons que le tableau est divisé à plusieurs reprises, puis fusionné pour obtenir un tableau trié. Avec ce concept à l’esprit, passons à l’implémentation de Mergesort dans le langage de programmation Java.

Implémentation de tri de fusion en Java

Nous pouvons implémenter la technique en Java en utilisant deux approches.

Tri de fusion itératif

C'est une approche ascendante. Les sous-tableaux d'un élément chacun sont triés et fusionnés pour former des tableaux à deux éléments. Ces tableaux sont ensuite fusionnés pour former des tableaux à quatre éléments et ainsi de suite. De cette façon, le tableau trié est construit en remontant.

L'exemple Java ci-dessous montre la technique itérative de tri par fusion.

import java.util.Arrays; class Main { // merge arrays : intArray[start...mid] and intArray[mid+1...end] public static void merge(int[] intArray, int[] temp, int start, int mid, int end) { int k = start, i = start, j = mid + 1; // traverse through elements of left and right arrays while (i <= mid && j <= end) { if (intArray[i] < intArray[j]) { temp[k++] = intArray[i++]; } else { temp[k++] = intArray[j++]; } } // Copy remaining elements while (i <= mid) { temp[k++] = intArray[i++]; } // copy temp array back to the original array to reflect sorted order for (i = start; i <= end; i++) { intArray[i] = temp[i]; } } // sorting intArray[low...high] using iterative approach public static void mergeSort(int[] intArray) { int low = 0; int high = intArray.length - 1; // sort array intArray[] using temporary array temp int[] temp = Arrays.copyOf(intArray, intArray.length); // divide the array into blocks of size m // m = [1, 2, 4, 8, 16...] for (int m = 1; m <= high - low; m = 2*m) { for (int i = low; i < high; i += 2*m) { int start = i; int mid = i + m - 1; int end = Integer.min(i + 2 * m - 1, high); //call merge routine to merge the arrays merge(intArray, temp, start, mid, end); } } } public static void main(String[] args) { //define array to be sorted int[] intArray = { 10,23,-11,54,2,9,-10,45 }; //print the original array System.out.println('Original Array : ' + Arrays.toString(intArray)); //call mergeSort routine mergeSort(intArray); //print the sorted array System.out.println('Sorted Array : ' + Arrays.toString(intArray)); } }

Production:

Baie d’origine: [10, 23, -11, 54, 2, 9, -10, 45]
Tableau trié: [-11, -10, 2, 9, 10, 23, 45, 54]

Tri de fusion itératif - Sortie

Tri de fusion récursif

Il s'agit d'une approche descendante. Dans cette approche, le tableau à trier est décomposé en tableaux plus petits jusqu'à ce que chaque tableau ne contienne qu'un seul élément. Ensuite, le tri devient facile à mettre en œuvre.

Le code Java suivant implémente l'approche récursive de la technique de tri par fusion.

import java.util.Arrays; public class Main { public static void merge_Sort(int[] numArray) { //return if array is empty if(numArray == null) { return; } if(numArray.length > 1) { int mid = numArray.length / 2; //find mid of the array // left half of the array int[] left = new int[mid]; for(int i = 0; i

Production:

Baie d’origine: [10, 23, -11, 54, 2, 9, -10, 45]
Tableau trié: [- 11, -10, 2, 9, 10, 23, 45, 54]

MergeSort récursif - Sortie

Dans la section suivante, passons des tableaux et utilisons la technique pour trier les structures de données des listes liées et des tableaux.

Trier la liste liée à l'aide du tri par fusion en Java

La technique de tri par fusion est la plus utilisée pour trier les listes liées. D'autres techniques de tri fonctionnent mal en ce qui concerne la liste chaînée en raison de son accès principalement séquentiel.

Le programme suivant trie une liste chaînée en utilisant cette technique.

import java.util.*; // A singly linked list node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } }; class Main { //two sorted linked list are merged together to form one sorted linked list public static Node Sorted_MergeSort(Node node1, Node node2) { //return other list if one is null if (node1 == null) return node2; else if (node2 == null) return node1; Node result; // Pick either node1 or node2, and recur if (node1.data <= node2.data) { result = node1; result.next = Sorted_MergeSort(node1.next, node2); } else { result = node2; result.next = Sorted_MergeSort(node1, node2.next); } return result; } //splits the given linked list into two halves public static Node[] FrontBackSplit(Node source) { // empty list if (source == null || source.next == null) { return new Node[]{ source, null } ; } Node slow_ptr = source; Node fast_ptr = source.next; // Advance 'fast' two nodes, and advance 'slow' one node while (fast_ptr != null) { fast_ptr = fast_ptr.next; if (fast_ptr != null) { slow_ptr = slow_ptr.next; fast_ptr = fast_ptr.next; } } // split the list at slow_ptr just before mid Node[] l_list = new Node[]{ source, slow_ptr.next }; slow_ptr.next = null; return l_list; } // use Merge sort technique to sort the linked list public static Node Merge_Sort(Node head) { // list is empty or has single node if (head == null || head.next == null) { return head; } // Split head into 'left' and 'right' sublists Node[] l_list = FrontBackSplit(head); Node left = l_list[0]; Node right = l_list[1]; // Recursively sort the sublists left = Merge_Sort(left); right = Merge_Sort(right); // merge the sorted sublists return Sorted_MergeSort(left, right); } // function to print nodes of given linked list public static void printNode(Node head) { Node node_ptr = head; while (node_ptr != null) { System.out.print(node_ptr.data + ' -> '); node_ptr = node_ptr.next; } System.out.println('null'); } public static void main(String[] args) { // input linked list int[] l_list = { 4,1,6,2,7,3,8 }; Node head = null; for (int key: l_list) { head = new Node(key, head); } //print the original list System.out.println('Original Linked List: '); printNode(head); // sort the list head = Merge_Sort(head); // print the sorted list System.out.println(' Sorted Linked List:'); printNode(head); } }

Production:

Liste liée d'origine:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> nul
Liste liée triée:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> nul

Sortie - Trier la liste liée

Trier ArrayList à l'aide du tri par fusion en Java

Comme les tableaux et les listes liées, nous pouvons également utiliser cette technique pour trier un ArrayList. Nous utiliserons des routines similaires pour diviser le ArrayList de manière récursive, puis fusionner les sous-listes.

Le code Java ci-dessous implémente la technique de tri de fusion pour ArrayList.

import java.util.ArrayList; class Main { //splits arrayList into sub lists. public static void merge_Sort(ArrayList numList){ int mid; ArrayList left = new ArrayList<>(); ArrayList right = new ArrayList<>(); if (numList.size() > 1) { mid = numList.size() / 2; // left sublist for (int i = 0; i numList, ArrayList left, ArrayList right){ //temporary arraylist to build the merged list ArrayList temp = new ArrayList<>(); //initial indices for lists int numbersIndex = 0; int leftIndex = 0; int rightIndex = 0; //traverse left and righ lists for merging while (leftIndex = left.size()) { temp = right; tempIndex = rightIndex; } else { temp = left; tempIndex = leftIndex; } for (int i = tempIndex; i numList = new ArrayList<>(); int temp; //populate the ArrayList with random numbers for (int i = 1; i <= 9; i++) numList.add( (int)(Math.random() * 50 + 1) ); //print original ArrayList of random numbers System.out.println('Original ArrayList:'); for(int val: numList) System.out.print(val + ' '); //call merge_Sort routine merge_Sort(numList); //print the sorted ArrayList System.out.println(' Sorted ArrayList:'); for(int ele: numList) System.out.print(ele + ' '); System.out.println(); } }

Production:

ArrayList d'origine:
17 40 36 7 6 23 35 2 38
Liste des tableaux triés:
2 6 7 17 23 35 36 38 40

Sortie - Trier ArrayList

Questions fréquemment posées

Q # 1) Le tri par fusion peut-il être effectué sans récursivité?

Répondre: Oui. Nous pouvons effectuer un tri de fusion non récursif appelé «tri de fusion itératif». Il s'agit d'une approche ascendante qui commence par fusionner des sous-tableaux avec un seul élément dans un sous-tableau de deux éléments.

Ensuite, ces sous-tableaux à 2 éléments sont fusionnés en sous-tableaux à 4 éléments et ainsi de suite en utilisant des constructions itératives. Ce processus se poursuit jusqu'à ce que nous ayons un tableau trié.

Q # 2) Le tri de fusion peut-il être effectué sur place?

Répondre: Le tri par fusion n'est généralement pas en place. Mais nous pouvons le mettre en place en utilisant une implémentation intelligente. Par exemple, en stockant la valeur de deux éléments à une position. Ceci peut être extrait par la suite en utilisant le module et la division.

Q # 3) Qu'est-ce qu'un tri par fusion à 3 voies?

Répondre: La technique que nous avons vue ci-dessus est un tri de fusion à 2 voies dans lequel nous divisons le tableau à trier en deux parties. Ensuite, nous trions et fusionnons le tableau.

Dans un tri de fusion à 3 voies, au lieu de diviser le tableau en 2 parties, nous le divisons en 3 parties, puis le trions et finalement le fusionnons.

Q # 4) Quelle est la complexité temporelle de Mergesort?

Répondre: La complexité temporelle globale du tri de fusion dans tous les cas est O (nlogn).

Q # 5) Où le tri Merge est-il utilisé?

Répondre: Il est principalement utilisé pour trier la liste chaînée en temps O (nlogn). Il est également utilisé dans des scénarios distribués dans lesquels de nouvelles données arrivent dans le système avant ou après le tri. Ceci est également utilisé dans divers scénarios de base de données.

Conclusion

Le tri par fusion est un tri stable et est effectué en divisant d'abord l'ensemble de données à plusieurs reprises en sous-ensembles, puis en triant et en fusionnant ces sous-ensembles pour former un ensemble de données trié. L'ensemble de données est divisé jusqu'à ce que chaque ensemble de données soit simple et facile à trier.

meilleure application pour espionner sur un autre téléphone

Nous avons vu les approches récursives et itératives de la technique de tri. Nous avons également discuté du tri de la structure de données Linked List et ArrayList à l'aide de Mergesort.

Nous continuerons avec la discussion sur plus de techniques de tri dans nos prochains tutoriels. Restez à l'écoute!

=> Visitez ici pour la série exclusive de didacticiels de formation Java.

lecture recommandée

^