{"id":4003,"date":"2024-08-08T17:45:07","date_gmt":"2024-08-08T15:45:07","guid":{"rendered":"https:\/\/www.capri-soft.de\/blog\/?p=4003"},"modified":"2024-08-09T14:42:45","modified_gmt":"2024-08-09T12:42:45","slug":"algorithmen-und-datenstrukturen-der-merge-sort-in-java","status":"publish","type":"post","link":"https:\/\/www.capri-soft.de\/blog\/?p=4003","title":{"rendered":"Algorithmen und Datenstrukturen: Der Merge Sort in Java"},"content":{"rendered":"\n

Der Algorithmus<\/h2>\n\n\n\n

Der MergeSort-Algorithmus ist ein stabiler Sortieralgorithmus nach dem Teile-und-Herrsche-Prinzip. Im ersten Teil wird das Array rekursiv so lange halbiert, bis in jeder Liste nur noch 1 Element vorhanden ist. Bei einer Liste mit einem Element geht man davon aus, dass die Liste automatisch als sortiert gilt. Danach k\u00f6nnen alle nachfolgenden Operationen von zwei sortierten Listen ausgehen, wodurch weniger Operationen beim Zusammenf\u00fchren ausreichen um ein neues sortiertes Array zu erhalten.<\/p>\n\n\n\n

Im zweiten Teil werden die bereits sortierten Listenh\u00e4lften verglichen und mit der Komplexit\u00e4t O(n) je rekursiver Iteration verglichen und zusammengef\u00fchrt (siehe den nachfolgenden JAVA Code).<\/p>\n\n\n\n

\"\"<\/a><\/figure>\n\n\n
\npackage AlgoDat;\n\npublic class MergeSort {\n    \/\/ Zu sortierendes Array\n    private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};\n\n    \/\/ H\u00e4lt die Klasse als instanziertes Objekt\n    @SuppressWarnings("unused")\n    private static MergeSort program;\n\n    \/\/ Hilfsfunktion f\u00fcr das Ausgeben des Arrays\n    public void OutputOfIntArray(int myArray[])\n    {\n        if (myArray != null)\n        {\n            for (int i = 0; i < myArray.length; i++) {\n                if (i > 0) System.out.print(";");\n                System.out.print(myArray[i]);\n            }\n\n            System.out.println();\n        }\n    }\n\n    public void mergeSort(int myArray[])\n    {\n        \/\/ zun\u00e4chst wird das Array ab der H\u00e4lfte in zwei\n        \/\/ Arrays links und rechts geteilt, das passiert\n        \/\/ rekursiv ... und zwar so lange bis jedes Element\n        \/\/ f\u00fcr sich nur noch 1x vorhanden ist (Teile-Herrsche-Prinzip).\n        \/\/ Das Teilen ist damit erledigt und nun sollte da\n        \/\/ Problem dadurch beherrschbarer werden -> nun \n        \/\/ werden die Einzelelemente wieder in Arrays sortiert. \n        \/\/ Die Abbruchbedingung der Rekursion ist, wenn die Liste \n        \/\/ nur noch ein einziges Element hat, wobei die Liste bei\n        \/\/ einem einzigem Element als sortiert gilt.\n        if (myArray.length == 1) return;\n\n        \/\/ weist bei ungeraden Zahlen eine abgerundete Ganzzahl zu\n        int indexHaelfte = myArray.length \/ 2;\n\n        int[] linkeHaelfte = new int[indexHaelfte];\n\n        \/\/ Die abgerundete Ganzzahl kann von der L\u00e4nge abgezogen werden\n        \/\/ um die Gr\u00f6\u00dfe des rechten Arrays zu erhalten.\n        int[] rechteHaelfte = new int[myArray.length - indexHaelfte];\n\n        \/\/ Bef\u00fclle die linke H\u00e4lfte \n        for (int i = 0; i < indexHaelfte; i++)\n        {\n            linkeHaelfte[i] = myArray[i];\n        }\n\n        \/\/ Bef\u00fclle die rechte H\u00e4lfte \n        for (int i = indexHaelfte; i < myArray.length; i++)\n        {\n            rechteHaelfte[i - indexHaelfte] = myArray[i];\n        }\n\n        \/\/ Hier ist der rekursive Aufruf, indem die beiden H\u00e4lften an\n        \/\/ die mergeSort-Methode selbst \u00fcbergeben wird.\n        this.mergeSort(linkeHaelfte);\n        this.mergeSort(rechteHaelfte);\n\n        \/\/ Hier werden die beiden Arrays wieder kombiniert (geMerged)\n        this.merge(myArray, linkeHaelfte, rechteHaelfte);\n    }\n\n    private void merge(int[] mergeArray, int[] linkeHaelfte, int[] rechteHaelfte)\n    {\n        System.out.print("Vergleiche linke H\u00e4lfte: ");\n        this.OutputOfIntArray(linkeHaelfte);\n        System.out.print("mit rechter H\u00e4lfte ");\n        this.OutputOfIntArray(rechteHaelfte);\n\n        int iteratorLinks = 0, iteratorRechts = 0, iteratorMergeArray = 0;\n\n        \/\/ Da die linke und reche H\u00e4lfte bereits sortiert sind, funktioniert die Zuweisung\n        \/\/ in ein neues Array mit einer einzigen Schleife der Komplexit\u00e4t\/Ordnung O(n).\n        while (iteratorLinks < linkeHaelfte.length && iteratorRechts < rechteHaelfte.length)\n        {\n            if (linkeHaelfte[iteratorLinks] <= rechteHaelfte[iteratorRechts])\n            {\n                mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];\n                iteratorLinks++;\n            }\n            else\n            {\n                mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];\n                iteratorRechts++;\n            }\n\n            iteratorMergeArray++;\n        }\n\n        \/\/ Wenn noch Elemente in der linken H\u00e4lfte waren, die nicht verglichen wurden,\n        \/\/ werden diese dem Merged Array hinzugef\u00fcgt\n        while (iteratorLinks < linkeHaelfte.length)\n        {\n            mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];\n            iteratorLinks++;\n            iteratorMergeArray++;\n        }\n\n        \/\/ Wenn noch Elemente in der rechten Array-H\u00e4lfte waren, die nicht verglichen wurden,\n        \/\/ werden diese dem Merged Array hinzugef\u00fcgt\n        while (iteratorRechts < rechteHaelfte.length)\n        {\n            mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];\n            iteratorRechts++;\n            iteratorMergeArray++;\n        }\n    }\n\n    \/\/ Konstruktor\n    public MergeSort()\n    {\n        System.out.print("Vorher: ");\n        this.OutputOfIntArray(myArray);\n\n        \/\/ Wir lagern alles weitere in eine eigene Methode aus, \n        \/\/ da MergeSort ein rekursiver Algorithmus ist, dessen \n        \/\/ Funktion aufgerufen werden muss und beeginnen mit dem \n        \/\/ unsortierten Array\n        this.mergeSort(myArray);\n\n        System.out.print("Nachher: ");\n        this.OutputOfIntArray(myArray);\n    }\n\n    public static void main(String[] args) \n    {\n        \/\/ Instanziere aus den statischem Programm ein echtes Objekt\n        \/\/ damit nicht alle Methoden und Variablen static sein m\u00fcssen.\n        program = new MergeSort();\n    }\n}\n<\/pre><\/div>\n\n\n
Ausgabe<\/h2>\n\n\n
\nVorher: 22;6;2;4;10;3;9;7;5;8;1\nVergleiche linke H\u00e4lfte: 22\nmit rechter H\u00e4lfte 6\nVergleiche linke H\u00e4lfte: 4\nmit rechter H\u00e4lfte 10\nVergleiche linke H\u00e4lfte: 2\nmit rechter H\u00e4lfte 4;10\nVergleiche linke H\u00e4lfte: 6;22\nmit rechter H\u00e4lfte 2;4;10\nVergleiche linke H\u00e4lfte: 9\nmit rechter H\u00e4lfte 7\nVergleiche linke H\u00e4lfte: 3\nmit rechter H\u00e4lfte 7;9\nVergleiche linke H\u00e4lfte: 8\nmit rechter H\u00e4lfte 1\nVergleiche linke H\u00e4lfte: 5\nmit rechter H\u00e4lfte 1;8\nVergleiche linke H\u00e4lfte: 3;7;9\nmit rechter H\u00e4lfte 1;5;8\nVergleiche linke H\u00e4lfte: 2;4;6;10;22\nmit rechter H\u00e4lfte 1;3;5;7;8;9\nNachher: 1;2;3;4;5;6;7;8;9;10;22\n<\/pre><\/div>\n\n\n
Komplexit\u00e4t: O-Notation (Ordnung)<\/h2>\n\n\n\n
Der MergeSort besteht aus 3 Teilen, die sich zu der Gesamtkomplexit\u00e4t zusammensetzen.<\/p>\n\n\n\n
Teil 1: (Rekursives) Teilen<\/h3>\n\n\n\n
Wenn wir ein Array der Gr\u00f6\u00dfe n<\/strong><\/em> in zwei H\u00e4lften teilen, ben\u00f6tigen wir <\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
Schritte. Hierbei handelt es sich um den Logarithmus dualis<\/strong>, also den Logarithmus zur Basis 2 (wessen Basis f\u00fcr die 2 H\u00e4lften spricht, in die aufgeteilt wird). Dies liegt also daran, dass wir die Liste in jeder Rekursionsebene halbieren. Wir fragen hier also mit welcher Zahl man 2 potenzieren muss um n zu erhalten. <\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
Wenn wir in dem unsortierten Array 11 Elemente haben, w\u00fcrden wir also fragen, mit welcher Zahl wir 2 potenzieren m\u00fcssen um 11 zu erhalten. Den Exponenten den wir hier erhalten w\u00e4re 4:<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
Wir runden die Kommazahl immer auf die n\u00e4chste volle Zahl auf, da wir keine halben Schritte machen k\u00f6nnen. Die Zahl 4 entspricht hier auch der Rekursionstiefe, die ben\u00f6tigt wird bis der aktuelle Rekursions-Heap nur noch aus einem Element bekommt, was zu Abbruch der Rekursion f\u00fchrt. <\/p>\n\n\n\n
Der erste Teil besitzt somit die Ordnung:<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
Teil 2 und 3: Sortieren und Mergen<\/h3>\n\n\n\n
Der Schritt des Zusammenf\u00fchrens (des Mergens) beider Liste ist mit der Sortierung kombiniert. Hier wird vorausgesetzt dass bereits sortierte Listenh\u00e4lften vorliegen, da man zwei bereits sortierte Arrays mit der Komplexit\u00e4t n vergleichen kann. Beim Zusammenf\u00fchren der sortierten Teillisten ben\u00f6tigen wir<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
Zeit. Dieser Schritt ist linear abh\u00e4ngig von der Gesamtanzahl der Elemente.<\/p>\n\n\n\n
Gesamt-Komplexit\u00e4t<\/h3>\n\n\n\n
Somit ergibt sich die Gesamtkomplexit\u00e4t:<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
im Worst-, Normal- und Best-Case. <\/p>\n\n\n\n
<\/p>\n