Lektion 49:bubble sortEs soll jetzt die erste Sortierfunktion geschrieben werden, die ein Array beliebiger Größe sortieren kann. Sehr bekannt ist das Sortierverfahren bubble sort. Der Kern dieses Verfahrens ist, während eines Durchlaufs jeweils jedes Array-Element mit seinem rechten Nachbarn zu vergleichen und gegebenenfalls auszutauschen. 6 1 3 2 7 5 4 ^ ^ 1 6 3 2 7 5 4 ^ ^ 1 3 6 2 7 5 4 ^ ^ 1 3 2 6 7 5 4 ^ ^ 1 3 2 6 7 5 4 ^ ^ 1 3 2 6 5 7 4 ^ ^ 1 3 2 6 5 4 7 Während dieses Durchlaufs hat sich im Array einiges getan. Was immer während eines Durchlaufs geschieht, ist daß der größte Wert nach ganz rechts wandert. Der größte Wert steigt sozusagen wie eine Luftblase (engl.: bubble) nach oben. Daher der lustige Name bubble sort. Im Beispiel ist jetzt die 7 nach ganz oben gestiegen. In einem zweiten Durchlauf, der nicht bis ganz zu Ende geführt werden muß, sondern nur bis direkt vor die 7, lassen wir den nächsten Wert aufsteigen. 1 3 2 6 5 4 7 ^ ^ 1 2 3 6 5 4 7 ^ ^ 1 2 3 6 5 4 7 ^ ^ 1 2 3 6 5 4 7 ^ ^ 1 2 3 5 6 4 7 ^ ^ 1 2 3 5 4 6 7 Jetzt ist die 6 nach oben gestiegen. Das, was wir bisher über das Verfahren festgestellt haben, läßt folgende Implementierung zu: Es ist fast immer sinnvoll, für kompliziertere Funktionen, die man schreibt, zusätzlich auch eine Testfunktion zu schreiben, die überprüft, ob die Funktion korrekt arbeitet. Das Verwenden von Zufallszahlen ist dabei recht sinnvoll, denn oft wird Ihre Funktion für die Werte, anhand derer Sie sich die Funktionsweise überlegt haben, bereits korrekt arbeiten, während es trotzdem noch Eingangsdaten geben mag, bei denen Fehler auftauchen. Wenn die zu schreibende Funktion fertig ist, dann kommentieren Sie die Testfunktion aus, lassen sie aber noch in der Datei stehen. Bei eventuell nötigen Änderungen können Sie dann jederzeit wieder auf die Testfunktion zurückgreifen.
Wir sortieren weiter und sehen zu, was passiert. 1 2 3 5 4 6 7 ^ ^ 1 2 3 5 4 6 7 ^ ^ 1 2 3 5 4 6 7 ^ ^ 1 2 3 4 5 6 7 ^ ^ 1 2 3 4 5 6 7 Jetzt ist die 5 an ihrem Platz. Zufällig ist auch das ganze Array sortiert. Das kann die Sortierfunktion leider nicht ohne größeren Aufwand feststellen. 1 2 3 4 5 6 7 ^ ^ 1 2 3 4 5 6 7 ^ ^ 1 2 3 4 5 6 7 ^ ^ 1 2 3 4 5 6 7 Jetzt ist auch die 4 an ihrem Platz. Weil das Array in diesem Durchlauf schon fertig sortiert war, hat kein Austausch stattgefunden. Das kann das Programm leicht feststellen. Sobald in einem Durchlauf kein Austausch stattgefunden hat, soll die Funktion beendet werden.
Ein anderes Beispiel: 2 3 4 5 1 6 7 8 9 ^ ^ 2 3 4 5 1 6 7 8 9 ^ ^ 2 3 4 5 1 6 7 8 9 ^ ^ 2 3 4 5 1 6 7 8 9 ^ ^ Austausch 2 3 4 1 5 6 7 8 9 ^ ^ 2 3 4 1 5 6 7 8 9 ^ ^ 2 3 4 1 5 6 7 8 9 ^ ^ 2 3 4 1 5 6 7 8 9 ^ ^ 2 3 4 5 1 6 7 8 9 In diesem Beispiel hat nur ein Austausch stattgefunden, und zwar bei pos==3. Daraus kann man direkt schließen, daß alle Elemente ab pos==4 nach dem Durchlauf fertig sortiert sind. Also braucht der nächste Durchlauf nur von pos==0 bis pos==2 (pos==3 wird dabei mitbehandelt, weil ja immer pos mit pos+1 verglichen wird) zu laufen. Wird dies eingebaut, dann darf die Variable austausch wieder entfallen.
Übung:Sortieren Sie mit bubble sort die folgende Zahlenfolge: 9 2 3 4 5 6 7 8 1 Weshalb greift hier die Optimierung nicht? Wie könnte man bubble sort verbessern, daß auch solche Zahlenfolgen schnell sortiert werden (schreiben Sie kein Programm, sondern beschreiben Sie nur die Programmidee)? Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern. [aktuelle Version] [inhalt] [index] [Fehlerkorrektur, Verbesserungsvorschlag] © Volkard Henkel <volkard@normannia.de>, last update: 08/25/00 |