{"id":3991,"date":"2024-08-06T22:22:37","date_gmt":"2024-08-06T20:22:37","guid":{"rendered":"https:\/\/www.capri-soft.de\/blog\/?p=3991"},"modified":"2024-08-07T08:55:08","modified_gmt":"2024-08-07T06:55:08","slug":"algorithmen-und-datenstrukturen-der-selection-sort-in-java","status":"publish","type":"post","link":"https:\/\/www.capri-soft.de\/blog\/?p=3991","title":{"rendered":"Algorithmen und Datenstrukturen: Der Selection Sort in Java"},"content":{"rendered":"\n

Der Algorithmus<\/h2>\n\n\n
\npackage AlgoDat;\n\npublic class SelectionSort {\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 SelectionSort 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 SelectionSort()\n    {\n        System.out.print("Vorher: ");\n        this.OutputOfIntArray(myArray);\n\n        \/\/ Laufe das zu sortierende Array von Anfang bis Ende durch\n        for (int idxSortierterBereich = 0; idxSortierterBereich < myArray.length - 1 ; idxSortierterBereich++)\n        {\n            \/\/ Starte an der Index-Position der \u00e4u\u00dfersten Schleife - davor ist schon alles sortiert\n            int indexPivotElement = idxSortierterBereich;\n\n            for (int idxUnsortierterBereich = idxSortierterBereich + 1; idxUnsortierterBereich < myArray.length; idxUnsortierterBereich++)\n            {\n                \/\/ ... und merke dir das kleinste Element\n                if (myArray[indexPivotElement] > myArray[idxUnsortierterBereich])\n                {\n                    indexPivotElement = idxUnsortierterBereich;\n                }\n            }\n\n            \/\/ Dieser Code tauscht das neu gefundene Minimum mit dem Element am aktuellen Index der \u00e4u\u00dferen Schleife                \n            int swapVar = myArray[indexPivotElement];\n            myArray[indexPivotElement] = myArray[idxSortierterBereich];\n            myArray[idxSortierterBereich] = swapVar;\n\n            System.out.print("Tausche: ");\n            this.OutputOfIntArray(myArray);\n        }\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 SelectionSort();\n    }\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\nTausche: 1;6;2;4;10;3;9;7;5;8;22\nTausche: 1;2;6;4;10;3;9;7;5;8;22\nTausche: 1;2;3;4;10;6;9;7;5;8;22\nTausche: 1;2;3;4;10;6;9;7;5;8;22\nTausche: 1;2;3;4;5;6;9;7;10;8;22\nTausche: 1;2;3;4;5;6;9;7;10;8;22\nTausche: 1;2;3;4;5;6;7;9;10;8;22\nTausche: 1;2;3;4;5;6;7;8;10;9;22\nTausche: 1;2;3;4;5;6;7;8;9;10;22\nTausche: 1;2;3;4;5;6;7;8;9;10;22\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
Zwei verschaltete Schleifen.
Die \u00e4u\u00dfere Schleife l\u00e4uft von 1 bis n;
Die innere Schleife l\u00e4uft vom Element der \u00e4u\u00dferen Schleife bis Schluss -> also n\/2, da der Bereich immer kleiner wird.<\/p>\n\n\n\n
O(T(n)) =   O(n\u00b2)<\/p>\n