Programm zur Zusammenführungssortierung in Java

Das Programm zur Zusammenführungssortierung in Java ist einer der am weitesten verbreiteten und effizientesten Algorithmen. Die Zusammenführungssortierung basiert auf der Divide-and-Conquer-Technik, bei der ein gegebenes Problem in mehrere Teilprobleme aufgeteilt und jedes Teilproblem unabhängig gelöst wird. Wenn die Teilprobleme gelöst sind, kombinieren wir ihre Ergebnisse, um die endgültige Lösung des Problems zu erhalten. Der Zusammenführungssortierungsalgorithmus kann mithilfe der Rekursion implementiert werden, da dabei mit Teilproblemen und nicht mit dem Hauptproblem gearbeitet wird.

Wie funktioniert die Zusammenführungssortierung?

Betrachten wir ein unsortiertes Array, das mithilfe des Merge-Sort-Algorithmus sortiert werden muss. Hier sind die Schritte zum Sortieren eines Arrays mit Werten: 18, 8, 4, 13, 10, 12, 7 und 11:

Starten Sie Ihren kostenlosen Softwareentwicklungskurs

Webentwicklung, Programmiersprachen, Softwaretests und andere

• Der erste Schritt besteht darin, ein Pivot-Element zu finden, auf dessen Grundlage unser Eingabearray in Unterarrays unterteilt wird.
• Nehmen wir an, dass Element 13 als Drehpunkt gewählt wird; Daher wird das ursprüngliche Array in zwei Unterarrays unterteilt. Das erste Unterarray enthält 18, 8, 4, 13 und das zweite Unterarray enthält die restlichen Elemente 10, 12, 7, 11.
• Die in Schritt 2 erhaltenen Unterarrays werden wie in Schritt 1 weiter unterteilt, und so geht es weiter.
• Sobald das Hauptarray in Unterarrays mit einzelnen Elementen unterteilt ist, beginnen wir erneut mit dem Zusammenführen dieser Unterarrays, sodass die zusammengeführten Elemente in sortierter Reihenfolge vorliegen.
• So funktioniert das eigentliche Teilen und Herrschen:

Programm zur Zusammenführungssortierung in Java

Hier ist ein Codebeispiel, das die Implementierung der Zusammenführungssortierung in Java zeigt:

Code:

package com.edubca.sorting;
public class MergeSort {
private int[] array;
private int[] tempMergedArr;
private int length;
public static void main(String a[]){
int[] inputArr = {18, 8, 4, 13, 10, 12, 7, 11};
MergeSort mergeSort = new MergeSort();
mergeSort.sort(inputArr);
for(int i:inputArr){
System.out.print(i + " ");
}
}
public void sort(int inputArr[]) {
this.array = inputArr;
this.length = inputArr.length;
this.tempMergedArr = new int[length];
performMergeSort(0, length - 1);
}
private void performMergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Sort the left side of the array call performMergeSort recursively
performMergeSort(lowerIndex, middle);
// Sort the right side of the array call performMergeSort recursively
performMergeSort(middle + 1, higherIndex);
// Merge subparts using a temporary array
mergeData(lowerIndex, middle, higherIndex);
}
}
private void mergeData (int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergedArr[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergedArr[i] <= tempMergedArr[j]) {
array[k] = tempMergedArr[i];
i++;
} else {
array[k] = tempMergedArr[j];
j++;
}
k++;
}
while (i <= middle) {
array[k] = tempMergedArr[i];
k++;
i++;
}
}
}

Der obige Code erzeugt ein sortiertes Array als Ausgabe.

Ausgabe:

Wann sollten wir die Zusammenführungssortierung verwenden?

Zusammenführungssortierung kann in den folgenden Szenarien verwendet werden:

• Wenn die zu sortierende Datenstruktur keinen Direktzugriff unterstützt, kann die Zusammenführungssortierung hilfreich und effizient sein.
• Wenn ein hohes Maß an Parallelität erforderlich ist, kann die Zusammenführungssortierung verwendet werden, da verschiedene Teilprobleme unabhängig voneinander mithilfe mehrerer parallel laufender Prozesse gelöst werden können.
• Die Zusammenführungssortierung geht bei der Arbeit mit verknüpften Listen schneller, da Zeiger beim Zusammenführen der Listen leicht geändert werden können.
• Merge Sort kann als stabile Sortierung betrachtet werden, was bedeutet, dass dasselbe Element in einem Array seine ursprünglichen Positionen zueinander beibehält. In Fällen, in denen eine hohe Stabilität erforderlich ist, kann man sich für die Zusammenführungssortierung entscheiden. 

Komplexitätsanalyse der Zusammenführungssortierung

Die folgenden Punkte analysieren die Komplexität der Zusammenführungssortierung:

• Merge Sort ist ein rekursiver Algorithmus und seine zeitliche Komplexität beträgt in allen drei Fällen (schlechtester, bester und durchschnittlicher) O(n*log n), da Merge Sort das Array in zwei gleiche Hälften teilt und lineare Zeit benötigt, um sie zusammenzuführen .
• Die Raumkomplexität der Zusammenführungssortierung beträgt O (n), da sie nach dem rekursiven Ansatz arbeitet. Daher kann die Zusammenführungssortierung als schneller, platz- und zeiteffizienter Algorithmus betrachtet werden.

Vergleich der Zusammenführungssortierung mit anderen Algorithmen

Die folgenden Punkte vergleichen die Zusammenführungssortierung mit anderen Algorithmen:

• Heap Sort hat die gleiche zeitliche Komplexität wie Merge Sort, erfordert jedoch nur O (1) Hilfsraum anstelle von O (n) von Merge Sort. Daher ist die Heap-Sortierung platzsparender als die Merge-Sortierung.
• Quick Sort-Implementierungen übertreffen im Allgemeinen die Zusammenführungssortierung beim Sortieren von RAM-basierten Arrays.
• Zusammenführungssortierung übertrifft Schnellsortierungs- und Heapsortierungsalgorithmen bei der Arbeit mit der verknüpften Liste, da Zeiger leicht geändert werden können.

Abschlussprogramm für Merge Sort in Java

Der Artikel kommt zu dem Schluss, dass die Zusammenführungssortierung ein wichtiges Konzept ist, das es zu verstehen gilt, wenn es um Algorithmen geht.

Das obige ist der detaillierte Inhalt vonProgramm zur Zusammenführungssortierung in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!