merge sort java program implement mergesort
Questo tutorial spiega cos'è l'ordinamento di unione in Java, l'algoritmo MergeSort, lo pseudo codice, l'implementazione dell'ordinamento di unione, esempi di mergeSort iterativo e ricorsivo:
La tecnica di ordinamento unione utilizza una strategia 'Divide-and-Conquer'. In questa tecnica, il set di dati da ordinare viene diviso in unità più piccole per ordinarlo.
=> Leggere attraverso la serie di formazione Easy Java.
Cosa imparerai:
- Unisci ordinamento in Java
- Conclusione
Unisci ordinamento in Java
Per esempio, se un array deve essere ordinato usando mergesort, allora l'array viene diviso attorno al suo elemento centrale in due sotto-array. Questi due sotto-array sono ulteriormente suddivisi in unità più piccole fino a quando non abbiamo solo 1 elemento per unità.
Una volta eseguita la divisione, questa tecnica unisce queste singole unità confrontando ogni elemento e ordinandole durante l'unione. In questo modo, quando l'intero array viene ricongiunto, otteniamo un array ordinato.
In questo tutorial, discuteremo tutti i dettagli di questa tecnica di ordinamento in generale, incluso il suo algoritmo e pseudo codici, nonché l'implementazione della tecnica in Java.
Algoritmo MergeSort in Java
Di seguito è riportato l'algoritmo per la tecnica.
# 1) Dichiarare un array myArray di lunghezza N
#Due) Controlla se N = 1, myArray è già ordinato
# 3) Se N è maggiore di 1,
- imposta sinistra = 0, destra = N-1
- compute middle = (sinistra + destra) / 2
- Chiama subroutine merge_sort (myArray, left, middle) => ordina la prima metà dell'array
- Chiama subroutine merge_sort (myArray, middle + 1, right) => questo ordinerà la seconda metà dell'array
- Chiama subroutine merge (myArray, left, middle, right) per unire gli array ordinati nei passaggi precedenti.
# 4) Uscita
Come visto nei passaggi dell'algoritmo, l'array è diviso in due al centro. Quindi ordiniamo ricorsivamente la metà sinistra dell'array e poi la metà destra. Dopo aver ordinato individualmente entrambe le metà, vengono unite insieme per ottenere un array ordinato.
Unisci ordinamento pseudo codice
Vediamo lo pseudo-codice per la tecnica Mergesort. Come già discusso poiché si tratta di una tecnica 'divide et impera', presenteremo le routine per dividere il set di dati e quindi unire i set di dati ordinati.
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 procedureNello pseudo-codice sopra, abbiamo due routine, ovvero Mergesort e merge. La routine Mergesort divide l'array di input in un array individuale abbastanza facile da ordinare. Quindi chiama la routine di unione.
La routine di unione unisce i singoli sotto-array e restituisce un array ordinato risultante. Dopo aver visto l'algoritmo e lo pseudo-codice per l'ordinamento Merge, illustriamo ora questa tecnica utilizzando un esempio.
Illustrazione di MergeSort
Considera il seguente array che deve essere ordinato utilizzando questa tecnica.
Ora, secondo l'algoritmo di ordinamento Merge, divideremo questo array nel suo elemento centrale in due sotto-array. Quindi continueremo a suddividere i sotto-array in array più piccoli fino a ottenere un singolo elemento in ogni array.
Una volta che ogni sotto-array contiene un solo elemento, uniamo gli elementi. Durante l'unione, confrontiamo gli elementi e ci assicuriamo che siano in ordine nell'array unito. Quindi lavoriamo fino a ottenere un array unito che viene ordinato.
Il processo è mostrato di seguito:
Come mostrato nell'illustrazione sopra, vediamo che l'array viene diviso ripetutamente e quindi unito per ottenere un array ordinato. Con questo concetto in mente, passiamo all'implementazione di Mergesort nel linguaggio di programmazione Java.
Implementazione dell'ordinamento di unione in Java
Possiamo implementare la tecnica in Java utilizzando due approcci.
Ordinamento di unione iterativo
Questo è un approccio dal basso verso l'alto. I sotto-array di un elemento ciascuno vengono ordinati e uniti per formare array a due elementi. Questi array vengono quindi uniti per formare array a quattro elementi e così via. In questo modo l'array ordinato viene costruito andando verso l'alto.
L'esempio Java seguente mostra la tecnica iterativa Merge Sort.
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)); } }Produzione:
Serie originale: (10, 23, -11, 54, 2, 9, -10, 45)
Array ordinato: (-11, -10, 2, 9, 10, 23, 45, 54)
Ordinamento di unione ricorsivo
Questo è un approccio dall'alto verso il basso. In questo approccio, l'array da ordinare viene suddiviso in array più piccoli finché ogni array contiene un solo elemento. Quindi l'ordinamento diventa facile da implementare.
Il seguente codice Java implementa l'approccio ricorsivo della tecnica di ordinamento 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 Produzione:
Serie originale: (10, 23, -11, 54, 2, 9, -10, 45)
Matrice ordinata: (- 11, -10, 2, 9, 10, 23, 45, 54)
Nella sezione successiva, passiamo dagli array e utilizziamo la tecnica per ordinare l'elenco collegato e le strutture dati dell'elenco di array.
Ordina elenco collegato utilizzando l'ordinamento di unione in Java
La tecnica di Mergesort è quella preferita per l'ordinamento di elenchi collegati. Altre tecniche di ordinamento funzionano male quando si tratta dell'elenco collegato a causa del suo accesso per lo più sequenziale.
Il seguente programma ordina un elenco collegato utilizzando questa tecnica.
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); } } Produzione:
Elenco collegato originale:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> nullo
Elenco collegato ordinato:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> nullo
qual è la subnet mask per un indirizzo IP di classe b?
Ordina ArrayList utilizzando Merge Sort in Java
Come gli array e gli elenchi collegati, possiamo anche utilizzare questa tecnica per ordinare un ArrayList. Useremo routine simili per dividere ArrayList in modo ricorsivo e quindi unire le sottoliste.
Il codice Java seguente implementa la tecnica di ordinamento 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(); } } Produzione:
Elenco array originale:
17 40 36 7 6 23 35 2 38
Elenco array ordinato:
2 6 7 17 23 35 36 38 40
Domande frequenti
D # 1) È possibile eseguire l'ordinamento Merge senza ricorsione?
Risposta: Sì. Possiamo eseguire un Merge sort non ricorsivo chiamato 'Merge sort iterativo'. Questo è un approccio dal basso verso l'alto che inizia fondendo sotto-array con un singolo elemento in un sotto-array di due elementi.
Quindi questi sotto-array a 2 elementi vengono uniti in sotto-array a 4 elementi e così via usando costrutti iterativi. Questo processo continua finché non abbiamo un array ordinato.
Q # 2) È possibile eseguire l'ordinamento di tipo Merge sul posto?
Risposta: L'ordinamento di unione generalmente non è sul posto. Ma possiamo farlo sul posto usando un'implementazione intelligente. Per esempio, memorizzando il valore di due elementi in una posizione. Questo può essere estratto in seguito utilizzando modulo e divisione.
Q # 3) Che cos'è un ordinamento a 3 vie?
Risposta: La tecnica che abbiamo visto sopra è un ordinamento Merge a 2 vie in cui dividiamo l'array da ordinare in due parti. Quindi ordiniamo e uniamo l'array.
In un ordinamento Merge a 3 vie, invece di dividere l'array in 2 parti, lo dividiamo in 3 parti, quindi lo ordiniamo e infine lo uniamo.
Q # 4) Qual è la complessità temporale di Mergesort?
Risposta: La complessità temporale complessiva dell'ordinamento Merge in tutti i casi è O (nlogn).
Q # 5) Dove viene utilizzato l'ordinamento Merge?
Risposta: Viene utilizzato principalmente per ordinare l'elenco collegato nel tempo O (nlogn). Viene anche utilizzato in scenari distribuiti in cui i nuovi dati arrivano nel sistema prima o dopo l'ordinamento. Viene utilizzato anche in vari scenari di database.
Conclusione
L'ordinamento di unione è un ordinamento stabile e viene eseguito prima suddividendo ripetutamente il set di dati in sottoinsiemi, quindi ordinando e unendo questi sottoinsiemi per formare un insieme di dati ordinato. Il set di dati viene suddiviso fino a quando ogni set di dati è banale e facile da ordinare.
Abbiamo visto gli approcci ricorsivi e iterativi alla tecnica di ordinamento. Abbiamo anche discusso l'ordinamento della struttura dati di Linked List e ArrayList utilizzando Mergesort.
Continueremo con la discussione di ulteriori tecniche di ordinamento nei nostri prossimi tutorial. Rimanete sintonizzati!
=> Visita qui per l'esclusiva serie di tutorial di formazione Java.
Lettura consigliata
- Unisci ordinamento in C ++ con esempi
- Come ordinare un array in Java - Tutorial con esempi
- Bubble Sort in Java - Algoritmi di ordinamento Java ed esempi di codice
- Ordina selezione in Java - Algoritmo di ordinamento selezione ed esempi
- Ordinamento di inserimento in Java - Algoritmo ed esempi di ordinamento di inserimento
- QuickSort in Java - Algoritmo, illustrazione e implementazione
- Array in Java 8 - Classe Stream e metodo ParallelSort
- Introduzione alle tecniche di ordinamento in C ++
