Dieser Algorithmus ist eine Erweiterung des normalen Bubble Sort Algorithmus. Wie dieser wird hierbei ein Array durchlaufen und das Element der aktuellen Iteration mit dem Nachfolgeelement getauscht, wenn dieses kleiner ist. Dadurch blubbern die Zahlen vom Array-Anfang bis zum Ende in einen sortierten Bereich auf der rechten Seite des Arrays nach oben.<\/p>\n\n\n\n
Der optimierte Bubble Sort-Algorithmus bricht weitere Iterationen ab, wenn er in in seiner if-Bedingung nichts mehr zum Tauschen gefunden hat. Dies vermerkt er in einer bool-Variable, was die umgebende do\u2026while-Schleife nutzt um den Algorithmus abzubrechen.<\/p>\n\n\n
\npackage AlgoDat;\n \npublic class OptimizedBubbleSort {\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 OptimizedBubbleSort 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 OptimizedBubbleSort()\n {\n System.out.print("Vorher: ");\n this.OutputOfIntArray(myArray);\n \n \/\/ Da wir eine do .. while-Schleife nun nutzen,\n \/\/ z\u00e4hlen wir einen Index darin runter um diesen\n \/\/ im Array jederzeit adressieren zu k\u00f6nnen.\n int sortierterBereichRechts = myArray.length;\n \n \/\/ Wenn in einer Iteration nix getauscht wurde\n \/\/ wird das f\u00fcr alle weiteren auch der Fall sein.\n \/\/ In dem Fall kann der Algorithmus enden.\n boolean hatteNochWasZuTun = false;\n \n do\n {\n \/\/ Am Anfang gibts nix zu tun\n hatteNochWasZuTun = false; \n \n System.out.println("Iteration: " + (myArray.length - sortierterBereichRechts + 1));\n \n for (int i = 0; i < sortierterBereichRechts - 1; i++)\n {\n if (myArray[i] > myArray[i + 1])\n {\n this.vertausche(myArray, i, i + 1);\n System.out.print("Tausche: ");\n this.OutputOfIntArray(myArray);\n hatteNochWasZuTun = true;\n }\n }\n \n \/\/ Der sortierte Bereich w\u00e4chst\n sortierterBereichRechts--;\n }\n while (hatteNochWasZuTun);\n \n System.out.print("Nachher: ");\n this.OutputOfIntArray(myArray);\n }\n \n public void vertausche(int[] arrayToSwap, int idx1, int idx2)\n {\n int swapVar = arrayToSwap[idx1];\n arrayToSwap[idx1] = arrayToSwap[idx2];\n arrayToSwap[idx2] = swapVar;\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 OptimizedBubbleSort();\n }\n}\n<\/pre><\/div>\n\n\nAusgabe<\/h2>\n\n\n\nVorher: 22;6;2;4;10;3;9;7;5;8;1\nIteration: 1\nTausche: 6;22;2;4;10;3;9;7;5;8;1\nTausche: 6;2;22;4;10;3;9;7;5;8;1\nTausche: 6;2;4;22;10;3;9;7;5;8;1\nTausche: 6;2;4;10;22;3;9;7;5;8;1\nTausche: 6;2;4;10;3;22;9;7;5;8;1\nTausche: 6;2;4;10;3;9;22;7;5;8;1\nTausche: 6;2;4;10;3;9;7;22;5;8;1\nTausche: 6;2;4;10;3;9;7;5;22;8;1\nTausche: 6;2;4;10;3;9;7;5;8;22;1\nTausche: 6;2;4;10;3;9;7;5;8;1;22\nIteration: 2\nTausche: 2;6;4;10;3;9;7;5;8;1;22\nTausche: 2;4;6;10;3;9;7;5;8;1;22\nTausche: 2;4;6;3;10;9;7;5;8;1;22\nTausche: 2;4;6;3;9;10;7;5;8;1;22\nTausche: 2;4;6;3;9;7;10;5;8;1;22\nTausche: 2;4;6;3;9;7;5;10;8;1;22\nTausche: 2;4;6;3;9;7;5;8;10;1;22\nTausche: 2;4;6;3;9;7;5;8;1;10;22\nIteration: 3\nTausche: 2;4;3;6;9;7;5;8;1;10;22\nTausche: 2;4;3;6;7;9;5;8;1;10;22\nTausche: 2;4;3;6;7;5;9;8;1;10;22\nTausche: 2;4;3;6;7;5;8;9;1;10;22\nTausche: 2;4;3;6;7;5;8;1;9;10;22\nIteration: 4\nTausche: 2;3;4;6;7;5;8;1;9;10;22\nTausche: 2;3;4;6;5;7;8;1;9;10;22\nTausche: 2;3;4;6;5;7;1;8;9;10;22\nIteration: 5\nTausche: 2;3;4;5;6;7;1;8;9;10;22\nTausche: 2;3;4;5;6;1;7;8;9;10;22\nIteration: 6\nTausche: 2;3;4;5;1;6;7;8;9;10;22\nIteration: 7\nTausche: 2;3;4;1;5;6;7;8;9;10;22\nIteration: 8\nTausche: 2;3;1;4;5;6;7;8;9;10;22\nIteration: 9\nTausche: 2;1;3;4;5;6;7;8;9;10;22\nIteration: 10\nTausche: 1;2;3;4;5;6;7;8;9;10;22\nIteration: 11\nNachher: 1;2;3;4;5;6;7;8;9;10;22\n<\/pre><\/div>\n\n\nKomplexit\u00e4t: O-Notation (Ordnung)<\/h2>\n\n\n\nWorst- und Average-Case<\/h3>\n\n\n\n
Wie beim normalen Bubble Sort betr\u00e4gt die Laufzeit-Komplexit\u00e4t im normalen und durchschnittlichen Fall\u00a0O(n\u00b2).<\/strong><\/p>\n\n\n\nBest-Case<\/h3>\n\n\n\n
Im Best-Case bricht der Algorithmus aber bereits nach einer Iteration ab, was einer Laufzeitkomplexit\u00e4t von\u00a0O(n)\u00a0<\/strong>entspricht.<\/p>\n