{"id":3969,"date":"2024-08-06T13:37:35","date_gmt":"2024-08-06T11:37:35","guid":{"rendered":"https:\/\/www.capri-soft.de\/blog\/?p=3969"},"modified":"2024-08-07T09:08:33","modified_gmt":"2024-08-07T07:08:33","slug":"algorithmen-und-datenstrukturen-der-insertion-sort-in-java","status":"publish","type":"post","link":"https:\/\/www.capri-soft.de\/blog\/?p=3969","title":{"rendered":"Algorithmen und Datenstrukturen: Der Insertion Sort in Java"},"content":{"rendered":"\n

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

Markant sind die zwei verschachtelten Schleifen, wobei die innere Schleife meistens eine While-Schleife mit 2 Bedingungen ist. Ein Index, welcher die Position der Trennung vom sortierten (links) und vom unsortierten (rechts) Bereich pr\u00e4sentiert, wird runtergez\u00e4hlt und das Array-Element an der Index-Position entspricht nach Ende der Schleife der Array-Position, mit der ein gemerktes Element getauscht werden kann. W\u00e4hrend der sortierte Bereich (immer links) mit dem ersten Element<\/em> des unsortierten Bereichs (immer rechts), welches sich gemerkt wird, verglichen wird, werden alle Elemente bis zu diesem Punkt um eins nach rechts ger\u00fcckt. Dadurch existiert die zu tauschende Position nach diesem Schritt zwei Mal und wird durch das gemerkte Element ausgetauscht.<\/p>\n\n\n\n

Die zweite Bedingung der inneren While-Schleife verhindert, das der runterz\u00e4hlende Index negativ wird. <\/p>\n\n\n

\npackage AlgoDat;\n\nclass InsertionSort {\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 InsertionSort als instanziertes Objekt\n    @SuppressWarnings("unused")\n    private static InsertionSort 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    \/\/ Konstruktor\n    public InsertionSort()\n    {\n        this.OutputOfIntArray(myArray);\n\n        \/\/ Bei 1 beginnen, da das Element mit dem Index 0 bereits als sortiert gilt \n        for (int idxSortierterBereich = 1; idxSortierterBereich < myArray.length; idxSortierterBereich++)\n        {\n            \/\/ Merke dir das erste Element vom unsortierten Bereich\n            int swapVar = myArray[idxSortierterBereich];\n            System.out.println("Gemerkt vor dem Aufr\u00fccken: " + swapVar);\n\n            \/\/ Das erste unsortierte Element auf der rechten Seite wird in den bereits sortierten Bereich \n            \/\/ auf der linken Seite eingef\u00fcgt, womit der unsortierte Bereich immer weiter nach rechts r\u00fcckt\n            \/\/ und dann verschwindet.\n            int idxUnsortierterBereich = idxSortierterBereich; \n            System.out.println("Der unsortierte Bereich beginnt bei Index: " + idxUnsortierterBereich);\n\n            \/\/ Laufe im Array von rechts nach links, so lange wie vorige Element noch gr\u00f6\u00dfer wie \n            \/\/ das erste Element vom unsortierten Bereich ist und der Bereich nicht negativ wird\n            while (idxUnsortierterBereich > 0 && myArray[idxUnsortierterBereich - 1] > swapVar)\n            {\n                \/\/ Alles eins nach rechts im Array r\u00fccken bis zum bereits sortierten Bereich\n                myArray[idxUnsortierterBereich] = myArray[idxUnsortierterBereich - 1] ;\n                idxUnsortierterBereich--;\n\n                System.out.print("Nach rechts aufr\u00fccken: ");\n                this.OutputOfIntArray(myArray);\n            }\n\n            System.out.println("Tausche Stelle " + (idxUnsortierterBereich + 1) + " (" + myArray[idxUnsortierterBereich] + \n            ") mit gemerkter Stelle " + (idxSortierterBereich + 1) + " (" + swapVar + ")");\n\n            myArray[idxUnsortierterBereich] = swapVar;\n\n            System.out.print("Getauscht: ");\n            this.OutputOfIntArray(myArray);\n        }\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 InsertionSort();\n    }\n}\n<\/pre><\/div>\n\n\n
Ausgabe<\/h2>\n\n\n
\n22;6;2;4;10;3;9;7;5;8;1\nGemerkt vor dem Aufr\u00fccken: 6\nDer unsortierte Bereich beginnt bei Index: 1\nNach rechts aufr\u00fccken: 22;22;2;4;10;3;9;7;5;8;1\nTausche Stelle 1 (22) mit gemerkter Stelle 2 (6)\nGetauscht: 6;22;2;4;10;3;9;7;5;8;1\nGemerkt vor dem Aufr\u00fccken: 2\nDer unsortierte Bereich beginnt bei Index: 2\nNach rechts aufr\u00fccken: 6;22;22;4;10;3;9;7;5;8;1\nNach rechts aufr\u00fccken: 6;6;22;4;10;3;9;7;5;8;1\nTausche Stelle 1 (6) mit gemerkter Stelle 3 (2)\nGetauscht: 2;6;22;4;10;3;9;7;5;8;1\nGemerkt vor dem Aufr\u00fccken: 4\nDer unsortierte Bereich beginnt bei Index: 3\nNach rechts aufr\u00fccken: 2;6;22;22;10;3;9;7;5;8;1\nNach rechts aufr\u00fccken: 2;6;6;22;10;3;9;7;5;8;1\nTausche Stelle 2 (6) mit gemerkter Stelle 4 (4)\nGetauscht: 2;4;6;22;10;3;9;7;5;8;1\nGemerkt vor dem Aufr\u00fccken: 10\nDer unsortierte Bereich beginnt bei Index: 4\nNach rechts aufr\u00fccken: 2;4;6;22;22;3;9;7;5;8;1\nTausche Stelle 4 (22) mit gemerkter Stelle 5 (10)\nGetauscht: 2;4;6;10;22;3;9;7;5;8;1\nGemerkt vor dem Aufr\u00fccken: 3\nDer unsortierte Bereich beginnt bei Index: 5\nNach rechts aufr\u00fccken: 2;4;6;10;22;22;9;7;5;8;1\nNach rechts aufr\u00fccken: 2;4;6;10;10;22;9;7;5;8;1\nNach rechts aufr\u00fccken: 2;4;6;6;10;22;9;7;5;8;1\nNach rechts aufr\u00fccken: 2;4;4;6;10;22;9;7;5;8;1\nTausche Stelle 2 (4) mit gemerkter Stelle 6 (3)\nGetauscht: 2;3;4;6;10;22;9;7;5;8;1\nGemerkt vor dem Aufr\u00fccken: 9\nDer unsortierte Bereich beginnt bei Index: 6\nNach rechts aufr\u00fccken: 2;3;4;6;10;22;22;7;5;8;1\nNach rechts aufr\u00fccken: 2;3;4;6;10;10;22;7;5;8;1\nTausche Stelle 5 (10) mit gemerkter Stelle 7 (9)\nGetauscht: 2;3;4;6;9;10;22;7;5;8;1\nGemerkt vor dem Aufr\u00fccken: 7\nDer unsortierte Bereich beginnt bei Index: 7\nNach rechts aufr\u00fccken: 2;3;4;6;9;10;22;22;5;8;1\nNach rechts aufr\u00fccken: 2;3;4;6;9;10;10;22;5;8;1\nNach rechts aufr\u00fccken: 2;3;4;6;9;9;10;22;5;8;1\nTausche Stelle 5 (9) mit gemerkter Stelle 8 (7)\nGetauscht: 2;3;4;6;7;9;10;22;5;8;1\nGemerkt vor dem Aufr\u00fccken: 5\nDer unsortierte Bereich beginnt bei Index: 8\nNach rechts aufr\u00fccken: 2;3;4;6;7;9;10;22;22;8;1\nNach rechts aufr\u00fccken: 2;3;4;6;7;9;10;10;22;8;1\nNach rechts aufr\u00fccken: 2;3;4;6;7;9;9;10;22;8;1\nNach rechts aufr\u00fccken: 2;3;4;6;7;7;9;10;22;8;1\nNach rechts aufr\u00fccken: 2;3;4;6;6;7;9;10;22;8;1\nTausche Stelle 4 (6) mit gemerkter Stelle 9 (5)\nGetauscht: 2;3;4;5;6;7;9;10;22;8;1\nGemerkt vor dem Aufr\u00fccken: 8\nDer unsortierte Bereich beginnt bei Index: 9\nNach rechts aufr\u00fccken: 2;3;4;5;6;7;9;10;22;22;1\nNach rechts aufr\u00fccken: 2;3;4;5;6;7;9;10;10;22;1\nNach rechts aufr\u00fccken: 2;3;4;5;6;7;9;9;10;22;1\nTausche Stelle 7 (9) mit gemerkter Stelle 10 (8)\nGetauscht: 2;3;4;5;6;7;8;9;10;22;1\nGemerkt vor dem Aufr\u00fccken: 1\nDer unsortierte Bereich beginnt bei Index: 10\nNach rechts aufr\u00fccken: 2;3;4;5;6;7;8;9;10;22;22\nNach rechts aufr\u00fccken: 2;3;4;5;6;7;8;9;10;10;22\nNach rechts aufr\u00fccken: 2;3;4;5;6;7;8;9;9;10;22\nNach rechts aufr\u00fccken: 2;3;4;5;6;7;8;8;9;10;22\nNach rechts aufr\u00fccken: 2;3;4;5;6;7;7;8;9;10;22\nNach rechts aufr\u00fccken: 2;3;4;5;6;6;7;8;9;10;22\nNach rechts aufr\u00fccken: 2;3;4;5;5;6;7;8;9;10;22\nNach rechts aufr\u00fccken: 2;3;4;4;5;6;7;8;9;10;22\nNach rechts aufr\u00fccken: 2;3;3;4;5;6;7;8;9;10;22\nNach rechts aufr\u00fccken: 2;2;3;4;5;6;7;8;9;10;22\nTausche Stelle 1 (2) mit gemerkter Stelle 11 (1)\nGetauscht: 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
O(T(n)) = O(n^2\/2+n\/2-n) = O(n^2\/2) = O (n^2)<\/p>\n\n\n\n
Die \u00e4u\u00dfere Schleife l\u00e4uft von 1 bis n-1, w\u00e4hrend die innere While-Schleife vom ersten Element des unsortierten Bereichs bis zu der Stelle der richtige Einf\u00fcgeposition l\u00e4uft. <\/p>\n\n\n\n
\u00c4u\u00dfere Schleife: Iteriert n-1 mal.
Innere Schleife: Iteriert 1x f\u00fcr Element 1, 2x f\u00fcr Element 2, 3x f\u00fcr Element 3, … n mal f\u00fcr Element n, was zu einer Laufzeit von<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
f\u00fchrt. Daraus folgt:<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
Additive Bestandteile, Faktoren und Konstanten fallen bei der Bestimmung der  Ordnung weg, daher ist die Ordnung O(n\u00b2). Die Dom\u00e4ne ist der dominante Teil der Ordnung – sie ist n\u00b2 .<\/p>\n\n\n\n
<\/p>\n