Menú

Merge Sort In Java: programa per implementar MergeSort

merge sort java program implement mergesort

Proveu El Nostre Instrument Per Eliminar Problemes

Aquest tutorial explica què és Merge Sort a Java, MergeSort Algorithm, Pseudo Code, Merge Sort Implementation, Exemples de Iterative & Recursive MergeSort:

La tècnica de classificació de combinació utilitza una estratègia 'Divideix i conquereix'. En aquesta tècnica, el conjunt de dades que es volen ordenar es divideix en unitats més petites per ordenar-lo.

=> Llegiu la sèrie de formació Java fàcil.

Combina la classificació a Java

Què aprendreu:

Combina la classificació a Java

Per exemple, si s'ha d'ordenar una matriu mitjançant mergesort, la matriu es divideix al voltant del seu element central en dos sub-matrius. Aquests dos subarrays es divideixen en unitats més petites fins que només tinguem 1 element per unitat.

Un cop feta la divisió, aquesta tècnica combina aquestes unitats individuals comparant cada element i ordenant-les en combinar-les. D'aquesta manera, quan es fusiona tota la matriu, obtenim una matriu ordenada.

En aquest tutorial, parlarem de tots els detalls d’aquesta tècnica d’ordenació en general, inclosos el seu algorisme i pseudo codis, així com la implementació de la tècnica a Java.

Algoritme MergeSort a Java

A continuació es mostra l’algorisme de la tècnica.

# 1) Declarar una matriu myArray de longitud N

# 2) Comproveu si N = 1, myArray ja està ordenat

# 3) Si N és superior a 1,

  • defineix a l'esquerra = 0, a la dreta = N-1
  • calcular mig = (esquerra + dreta) / 2
  • Crida a la subrutina merge_sort (myArray, esquerra, mig) => ordena la primera meitat de la matriu
  • Crida a la subrutina merge_sort (myArray, middle + 1, right) => això ordenarà la segona meitat de la matriu
  • Truqueu a la combinació de subrutines (myArray, esquerra, mig, dreta) per combinar matrius ordenats en els passos anteriors.

# 4) Surt

Tal com es veu als passos de l'algorisme, la matriu es divideix en dues al centre. A continuació, ordenem recursivament la meitat esquerra de la matriu i després la meitat dreta. Un cop ordenem individualment les dues meitats, es combinen per obtenir una matriu ordenada.

Combina el pseudocodi d'ordenació

Vegem el pseudocodi de la tècnica Mergesort. Com ja s’ha comentat, ja que es tracta d’una tècnica de “dividir i conquerir”, presentarem les rutines per dividir el conjunt de dades i, a continuació, combinar els conjunts de dades ordenats.

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

Al pseudocodi anterior, tenim dues rutines, és a dir, Mergesort i merge. La rutina Mergesort divideix la matriu d’entrada en una matriu individual prou fàcil d’ordenar. A continuació, anomena la rutina de combinació.

La rutina de combinació combina les sub-matrius individuals i retorna una matriu ordenada resultant. Després d’haver vist l’algorisme i el pseudocodi per a la combinació, ara il·lustrem aquesta tècnica amb un exemple.

Il·lustració MergeSort

Penseu en la següent matriu que s’ha d’ordenar amb aquesta tècnica.

Combina la il·lustració d

Ara, d'acord amb l'algorisme de classificació Merge, dividirem aquesta matriu en el seu element mitjà en dues sub-matrius. Després continuarem dividint les sub-matrius en matrius més petites fins que obtinguem un sol element a cada matriu.

Un cop cada sub-matriu només conté un element, fusionem els elements. Mentre combinem, comparem els elements i ens assegurem que estiguin en ordre a la matriu combinada. Així doncs, treballem fins a obtenir una matriu combinada ordenada.

El procés es mostra a continuació:

Combina el procés d

Com es mostra a la il·lustració anterior, veiem que la matriu es divideix repetidament i després es fusiona per obtenir una matriu ordenada. Amb aquest concepte en ment, passem a la implementació de Mergesort en llenguatge de programació Java.

Combina la implementació de l'ordenació a Java

Podem implementar la tècnica a Java mitjançant dos enfocaments.

Classificació de combinació iterativa

Es tracta d’un enfocament ascendent. Les sub-matrius d’un element cadascuna s’ordenen i es combinen per formar matrius de dos elements. Aquestes matrius es combinen per formar matrius de quatre elements, etc. D'aquesta manera, la matriu ordenada es construeix pujant cap amunt.

A l'exemple següent de Java es mostra la tècnica iterativa d'ordenació de combinació.

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)); } }

Sortida:

Matriu original: (10, 23, -11, 54, 2, 9, -10, 45)
Matriu ordenada: (-11, -10, 2, 9, 10, 23, 45, 54)

Classificació de combinació iterativa: sortida

Classificació de combinació recursiva

Es tracta d’un enfocament de dalt a baix. En aquest enfocament, la matriu que cal ordenar es desglossa en matrius més petits fins que cada matriu només conté un element. Aleshores, la classificació es fa fàcil d’implementar.

El següent codi Java implementa l'enfocament recursiu de la tècnica de classificació Merge.

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

Sortida:

Matriu original: (10, 23, -11, 54, 2, 9, -10, 45)
Matriu ordenada: (- 11, -10, 2, 9, 10, 23, 45, 54)

MergeSort recursiu: sortida

A la secció següent, canviem de matrius i fem servir la tècnica per ordenar les estructures de dades de la llista enllaçada i de la llista de matrius.

Ordeneu la llista enllaçada mitjançant la combinació d'ordenacions a Java

La tècnica Mergesort és la més preferida per ordenar llistes enllaçades. Altres tècniques d’ordenació funcionen malament quan es tracta de la llista enllaçada a causa del seu accés majoritàriament seqüencial.

El programa següent ordena una llista enllaçada mitjançant aquesta tècnica.

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); } }

Sortida:

Llista enllaçada original:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> nul
Llista enllaçada ordenada:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> nul

implementació d’arbre binari c ++

Sortida - Ordena la llista enllaçada

Ordeneu ArrayList mitjançant la combinació d'ordenacions a Java

Igual que Arrays i llistes enllaçades, també podem utilitzar aquesta tècnica per ordenar una ArrayList. Utilitzarem rutines similars per dividir l'ArrayList recursivament i després fusionarem les sublistes.

El codi Java següent implementa la tècnica de classificació Merge per 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(); } }

Sortida:

Llista de matrius original:
17 40 36 7 6 23 35 2 38
Llista de matrius ordenada:
2 6 7 17 23 35 36 38 40

Sortida: ordena la llista de matrius

Preguntes freqüents

P # 1) Es pot fer la classificació de combinació sense recursivitat?

Resposta: Sí. Podem realitzar un tipus de combinació no recursiu anomenat ‘sort iterative Merge sort’. Aquest és un enfocament ascendent que comença fusionant sub-matrius amb un sol element en un sub-array de dos elements.

A continuació, aquests subarrays de 2 elements es combinen en subarrays de 4 elements i així successivament mitjançant construccions iteratives. Aquest procés continua fins que tenim una matriu ordenada.

Q # 2) Es pot fer la classificació de combinació al seu lloc?

Resposta: La classificació de combinació generalment no està al seu lloc. Però podem fer-ho al seu lloc mitjançant una implementació intel·ligent. Per exemple, emmagatzemant el valor de dos elements en una posició. Això es pot extreure després mitjançant el mòdul i la divisió.

Q # 3) Què és un tipus de combinació de 3 vies?

Resposta: La tècnica que hem vist anteriorment és un tipus de combinació bidireccional en què dividim la matriu per ordenar-la en dues parts. A continuació, ordenem i combinem la matriu.

En un ordre de combinació de 3 vies, en lloc de dividir la matriu en 2 parts, la dividim en 3 parts, després l’ordenem i, finalment, la fusionem.

Q # 4) Quina és la complexitat horària de Mergesort?

Resposta: La complexitat temporal general de la classificació Merge en tots els casos és O (nlogn).

Q # 5) On s’utilitza el tipus Merge?

Resposta: S'utilitza principalment per ordenar la llista enllaçada en temps O (nlogn). També s’utilitza en escenaris distribuïts en què apareixen noves dades al sistema abans o després de l’ordenació. Això també s'utilitza en diversos escenaris de bases de dades.

Conclusió

La combinació d'ordenació és una classificació estable i es realitza dividint primer el conjunt de dades repetidament en subconjunts i després ordenant i fusionant aquests subconjunts per formar un conjunt de dades ordenat. El conjunt de dades es divideix fins que cada conjunt de dades és trivial i fàcil d’ordenar.

Hem vist els enfocaments recursius i iteratius de la tècnica de classificació. També hem debatut sobre l’ordenació de l’estructura de dades Linked List i ArrayList mitjançant Mergesort.

Continuarem amb el debat sobre més tècniques d’ordenació als nostres propers tutorials. Estigueu atents!

=> Visiteu aquí la sèrie exclusiva de cursos de formació de Java.

Lectura recomanada

^