Zusammenführungssortierung in Java

Was ist Zusammenführungssortierung?

Die Zusammenführungssortierung ist der gebräuchlichste Algorithmus zum Sortieren von Daten mithilfe der „ Teile-und-Herrsche “-Technik. Bei diesem Algorithmus wird das Problem in Teilprobleme unterteilt und diese nach dem Sortieren zusammengeführt. Nehmen wir an, wir haben eine Liste unsortierter Zahlen, das Ergebnis einer Klasse für ein bestimmtes Thema. Um sie in aufsteigender Reihenfolge zu sortieren, müssen wir sie in einer Liste beginnend von niedrig nach hoch platzieren. Bei diesem Merge-Sort-Algorithmus wird die Liste in kleinere Listen unterteilt, um sie in aufsteigender Reihenfolge zu sortieren, und dann werden die Ergebnisse zum besseren Verständnis zusammengeführt. Merge Sort in Java kann am Beispiel eines Arrays {6,9,8,2,4,1} erklärt werden. Betrachten Sie es als Ergebnis eines Klassentests von 10. Das Array (der Ergebnisse) wird wiederholt geteilt in kleinere Stücke, bis sie die Größe 1 haben. Anschließend erfolgt der Zusammenführungsprozess bei gleichzeitiger Sortierung der Zahlen. Dadurch erhalten wir ein Ergebnis, das von der niedrigsten bis zur höchsten Note reicht. Dieses Array wird in zwei Arrays unterteilt, die jeweils 3 Elemente enthalten, wie unten in Schritt 2 gezeigt , und es wird weiter geteilt, bis in Schritt 4 die Einheit erreicht wird . Dann beginnt der Merge-Sort-Algorithmus, die Zahlen Schritt für Schritt zu sortieren ( Schritt 5 ) und führt die Zahlen dann in den Schritten 6 und 7 zu einem größeren Array zusammen .

Implementierung

In der Implementierung werden wir Code für den Merge-Sort-Algorithmus in Java schreiben. Die erforderlichen Variablen sind das Eingabearray und die Länge des Arrays. Diese beiden Parameter werden weiterhin verwendet, um weitere Parameter einzuführen, um die Zusammenführungssortierfunktion zu erstellen. Schauen wir uns den folgenden Ausschnitt an, um die allgemeine Funktionsweise des Merge-Sort-Algorithmus in Java zu verstehen.

Merge_Sort_Algo (Array, Beginning, End)
/** Three parameters required for the Merge Sort Algorithm
 * Array = values of the array
 * Beginning = the starting element of the array
 * End = the ending element of the array*/

if (Beginning < End) // condition check Beginning must be less than End

set Middle = (Beginning + End) / 2 // Assigning Middle to the array

Merge_Sort_Algo (Array, Beginning, Middle) /** Sorting and merging of elements from Beginning to the Middle */

Merge_Sort_Algo (Array, Middle +1, End) /** Sorting and merging of elements from Middle to the End */

Merge (Array, Beginning, Middle, End) // Merging both the sorted arrays

end of if

End Merge_Sort_Algo

Zuerst werden durch die if-Bedingung Anfang und Ende verwendet, um die Mitte zu bestimmen. Dann werden im nächsten Schritt zwei neue Subarrays erstellt, beginnend vom Anfang bis zur Mitte und das andere beginnend von der Mitte +1 bis zum Ende. Diese Arrays werden geteilt, bis ihre Länge 1 wird, und dann werden durch die Zusammenführungsfunktion die sortierten Unterarrays Anfang, Mitte, Mitte+1 und Ende alle wieder zusammengeführt, um die Lösung zu erhalten.

Beispiel

Der folgende Code in Java erklärt den Merge-Sort-Algorithmus:

import java.util.Arrays;

class HelloWorld {

    public static void merge(

  int[] array, int[] new_array_1, int[] new_array_2, int left, int right) {
   // defining parameters

    int i = 0, j = 0, k = 0;

    while (i < left && j < right) {  // conditions for merging

        if (new_array_1[i] <= new_array_2[j]) {
            array[k++] = new_array_1[i++];
        }
        else {
            array[k++] = new_array_2[j++];
        }
    }

    while (i < left) {
        array[k++] = new_array_1[i++];
    }

    while (j < right) {
        array[k++] = new_array_2[j++];
    }
}

    public static void mergeSort(int[] array, int length) { /** required parameters */
	if (length < 2) {  //condition for the length of array
    	return;
	}

	int middle = length / 2;  // defining new parameter middle

	int [ ] new_array_1 = new int [middle]; /** defining the new first array after division */
	int [ ] new_array_2 = new int [length - middle]; /** defining the new second array */


	for (int i = 0; i < middle; i++) { /**applying condition for sorting of new array 1 */
    	new_array_1 [ i ] = array [ i ];
	}

	for (int i = middle; i < length ; i++) { /**applying condition for sorting of new array 2 */
    	new_array_2 [ i - middle] = array [ i ];
	}

	mergeSort (new_array_1, middle); /** calling merge sort function for new array 1 */
	mergeSort (new_array_2, length - middle); /** calling merge sort function for new array 2 */


	merge(array, new_array_1, new_array_2, middle, length - middle); /** calling function for merging of new array 1 and new array 2 */
}


    public static void main(String[] args) {

        int [ ] testScores = {6,9,8,2,4,1};
        int size = testScores.length;

        System.out.println("Original Array " + Arrays.toString(testScores) + "\n");

        mergeSort(testScores, size);

        System.out.println("After Merge Sort " + Arrays.toString(testScores) + "\n");
    }
}

Ausgabe

Abschluss

Merge Sort in Java ist ein einfacher Algorithmus zum Erfassen einer sortierten Liste aus einer unsortierten Liste von Zahlen. Die grundlegende Methode „ Teile und herrsche “ wird angewendet, um von einem unsortierten Array aus auf das sortierte Array zuzugreifen.