merge sort java program implement mergesort
Dieses Tutorial erklärt, was Merge Sort in Java ist, MergeSort-Algorithmus, Pseudocode, Merge Sort-Implementierung, Beispiele für iteratives und rekursives MergeSort:
Die Zusammenführungssortiertechnik verwendet eine 'Teilen und Erobern' -Strategie. Bei dieser Technik wird der zu sortierende Datensatz in kleinere Einheiten unterteilt, um ihn zu sortieren.
=> Lesen Sie die Easy Java Training Series durch.
Was du lernen wirst:
- Sortierung in Java zusammenführen
- Fazit
Sortierung in Java zusammenführen
Zum Beispiel, Wenn ein Array mithilfe von Mergesort sortiert werden soll, wird das Array um sein mittleres Element in zwei Unterarrays unterteilt. Diese beiden Unterarrays sind weiter in kleinere Einheiten unterteilt, bis wir nur noch 1 Element pro Einheit haben.
Sobald die Division abgeschlossen ist, führt diese Technik diese einzelnen Einheiten zusammen, indem jedes Element verglichen und beim Zusammenführen sortiert wird. Auf diese Weise erhalten wir zu dem Zeitpunkt, an dem das gesamte Array wieder zusammengeführt wird, ein sortiertes Array.
In diesem Tutorial werden alle Details dieser Sortiertechnik im Allgemeinen einschließlich des Algorithmus und der Pseudocodes sowie die Implementierung der Technik in Java erläutert.
MergeSort-Algorithmus in Java
Es folgt der Algorithmus für die Technik.
# 1) Deklarieren Sie ein Array myArray der Länge N.
#zwei) Überprüfen Sie, ob N = 1 ist, myArray ist bereits sortiert
#3) Wenn N größer als 1 ist,
- setze links = 0, rechts = N-1
- berechne Mitte = (links + rechts) / 2
- Rufen Sie das Unterprogramm merge_sort (myArray, left, middle) => auf, um die erste Hälfte des Arrays zu sortieren
- Rufen Sie die Unterroutine merge_sort (myArray, Mitte + 1, rechts) auf => Dadurch wird die zweite Hälfte des Arrays sortiert
- Rufen Sie die Unterprogrammzusammenführung (myArray, links, Mitte, rechts) auf, um die in den obigen Schritten sortierten Arrays zusammenzuführen.
# 4) Ausgang
Wie in den Algorithmusschritten zu sehen ist, ist das Array in der Mitte zweigeteilt. Dann sortieren wir rekursiv die linke Hälfte des Arrays und dann die rechte Hälfte. Sobald wir beide Hälften einzeln sortiert haben, werden sie zusammengeführt, um ein sortiertes Array zu erhalten.
Sortier-Pseudocode zusammenführen
Sehen wir uns den Pseudocode für die Mergesort-Technik an. Wie bereits erwähnt, werden wir die Routinen zum Teilen des Datensatzes und zum anschließenden Zusammenführen der sortierten Datensätze vorstellen, da dies eine 'Divide-and-Conquer' -Technik ist.
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
Im obigen Pseudocode haben wir zwei Routinen, d. H. Zusammenführen und Zusammenführen. Die Routine Mergesort teilt das Eingabearray in ein einzelnes Array auf, das leicht zu sortieren ist. Dann ruft es die Zusammenführungsroutine auf.
Die Zusammenführungsroutine führt die einzelnen Unterarrays zusammen und gibt ein resultierendes sortiertes Array zurück. Nachdem wir den Algorithmus und den Pseudocode für die Sortierung zum Zusammenführen gesehen haben, wollen wir diese Technik nun anhand eines Beispiels veranschaulichen.
MergeSort Illustration
Betrachten Sie das folgende Array, das mit dieser Technik sortiert werden soll.
Nach dem Sortieralgorithmus 'Zusammenführen' teilen wir dieses Array an seinem mittleren Element in zwei Unterarrays auf. Dann werden wir die Unterarrays weiter in kleinere Arrays aufteilen, bis wir in jedem Array ein einzelnes Element erhalten.
Sobald jedes Subarray nur ein Element enthält, führen wir die Elemente zusammen. Beim Zusammenführen vergleichen wir die Elemente und stellen sicher, dass sie im zusammengeführten Array in Ordnung sind. Also arbeiten wir uns hoch, um ein zusammengeführtes Array zu erhalten, das sortiert ist.
Der Prozess ist unten gezeigt:
Wie in der obigen Abbildung gezeigt, wird das Array wiederholt geteilt und dann zusammengeführt, um ein sortiertes Array zu erhalten. Lassen Sie uns vor diesem Hintergrund mit der Implementierung von Mergesort in der Programmiersprache Java fortfahren.
Implementierung der Zusammenführungssortierung in Java
Wir können die Technik in Java mit zwei Ansätzen implementieren.
Iterative Zusammenführungssortierung
Dies ist ein Bottom-up-Ansatz. Die Unterarrays von jeweils einem Element werden sortiert und zu Arrays mit zwei Elementen zusammengeführt. Diese Arrays werden dann zusammengeführt, um Arrays mit vier Elementen usw. zu bilden. Auf diese Weise wird das sortierte Array nach oben erstellt.
Das folgende Java-Beispiel zeigt die iterative Zusammenführungssortiertechnik.
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)); } }
Ausgabe:
Ursprüngliches Array: [10, 23, -11, 54, 2, 9, -10, 45]
Sortiertes Array: [-11, -10, 2, 9, 10, 23, 45, 54]
Rekursive Zusammenführungssortierung
Dies ist ein Top-Down-Ansatz. Bei diesem Ansatz wird das zu sortierende Array in kleinere Arrays zerlegt, bis jedes Array nur noch ein Element enthält. Dann wird die Sortierung einfach zu implementieren.
Der folgende Java-Code implementiert den rekursiven Ansatz der Merge-Sortiertechnik.
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 Ausgabe:
Ursprüngliches Array: [10, 23, -11, 54, 2, 9, -10, 45]
Sortiertes Array: [- 11, -10, 2, 9, 10, 23, 45, 54]
Wechseln wir im nächsten Abschnitt von Arrays und verwenden Sie die Technik, um die Datenstrukturen der verknüpften Liste und der Array-Liste zu sortieren.
Verknüpfte Liste mit Zusammenführungssortierung in Java sortieren
Die Mergesort-Technik ist die am meisten bevorzugte zum Sortieren verknüpfter Listen. Andere Sortiertechniken sind in Bezug auf die verknüpfte Liste aufgrund ihres meist sequentiellen Zugriffs schlecht.
Das folgende Programm sortiert eine verknüpfte Liste mit dieser Technik.
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); } }
Ausgabe:
Ursprüngliche verknüpfte Liste:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> null
Sortierte verknüpfte Liste:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> null
Fragen und Antworten zum HTML5-Interview pdf
Sortieren der ArrayList mithilfe der Zusammenführungssortierung in Java
Wie Arrays und verknüpfte Listen können wir diese Technik auch zum Sortieren einer ArrayList verwenden. Wir werden ähnliche Routinen verwenden, um die ArrayList rekursiv zu teilen und dann die Unterlisten zusammenzuführen.
Der folgende Java-Code implementiert die Merge-Sortiertechnik für 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(); } }
Ausgabe:
Ursprüngliche ArrayList:
17 40 36 7 6 23 35 2 38
Sortierte ArrayList:
2 6 7 17 23 35 36 38 40
Häufig gestellte Fragen
F # 1) Kann die Zusammenführungssortierung ohne Rekursion durchgeführt werden?
Antworten: Ja. Wir können eine nicht rekursive Zusammenführungssortierung durchführen, die als 'iterative Zusammenführungssortierung' bezeichnet wird. Dies ist ein Bottom-up-Ansatz, bei dem zunächst Unterarrays mit einem einzelnen Element zu einem Unterarray aus zwei Elementen zusammengeführt werden.
Dann werden diese 2-Element-Unterarrays unter Verwendung iterativer Konstrukte zu 4-Element-Unterarrays usw. zusammengeführt. Dieser Prozess wird fortgesetzt, bis wir ein sortiertes Array haben.
Q # 2) Kann die Sortierung zusammengeführt werden?
Antworten: Die Zusammenführungssortierung ist im Allgemeinen nicht vorhanden. Aber wir können es schaffen, indem wir eine clevere Implementierung verwenden. Zum Beispiel, durch Speichern von zwei Elementen Wert an einer Position. Dies kann anschließend mit Modul und Division extrahiert werden.
Q # 3) Was ist eine 3-Wege-Zusammenführungssorte?
Antworten: Die Technik, die wir oben gesehen haben, ist eine 2-Wege-Zusammenführungssortierung, bei der wir das zu sortierende Array in zwei Teile aufteilen. Dann sortieren und führen wir das Array zusammen.
Bei einer 3-Wege-Zusammenführungssortierung teilen wir das Array nicht in zwei Teile auf, sondern teilen es in drei Teile auf, sortieren es und führen es schließlich zusammen.
Q # 4) Was ist die zeitliche Komplexität von Mergesort?
Antworten: Die Gesamtzeitkomplexität der Zusammenführungssortierung beträgt in allen Fällen O (nlogn).
Q # 5) Wo wird die Zusammenführungssorte verwendet?
Antworten: Es wird hauptsächlich zum Sortieren der verknüpften Liste in O (nlogn) -Zeit verwendet. Es wird auch in verteilten Szenarien verwendet, in denen neue Daten vor oder nach dem Sortieren im System eingehen. Dies wird auch in verschiedenen Datenbankszenarien verwendet.
Fazit
Die Zusammenführungssortierung ist eine stabile Sortierung und wird durchgeführt, indem zuerst der Datensatz wiederholt in Teilmengen aufgeteilt wird und diese Teilmengen dann sortiert und zusammengeführt werden, um einen sortierten Datensatz zu bilden. Der Datensatz wird aufgeteilt, bis jeder Datensatz trivial und einfach zu sortieren ist.
Wir haben die rekursiven und iterativen Ansätze für die Sortiertechnik gesehen. Wir haben auch die Sortierung der verknüpften Liste und der ArrayList-Datenstruktur mithilfe von Mergesort erörtert.
Wir werden mit der Diskussion weiterer Sortiertechniken in unseren kommenden Tutorials fortfahren. Bleiben Sie dran!
=> Besuchen Sie hier für die exklusive Java Training Tutorial-Reihe.
Literatur-Empfehlungen
- Sortierung in C ++ mit Beispielen zusammenführen
- So sortieren Sie ein Array in Java - Tutorial mit Beispielen
- Blasensortierung in Java - Java-Sortieralgorithmen und Codebeispiele
- Auswahlsortierung in Java - Auswahlsortierungsalgorithmus und Beispiele
- Einfügungssortierung in Java - Einfügungssortierungsalgorithmus und Beispiele
- QuickSort In Java - Algorithmus, Illustration & Implementierung
- Arrays in Java 8 - Stream-Klasse und ParallelSort-Methode
- Einführung in Sortiertechniken in C ++