Theorieteil zu Folge 8

Analyse des Zeitverhaltens der Sortieralgorithmen

Bubblesort

Best-Case

Im günstigsten Fall sind die Zahlen bereits sortiert - der Bubblesort weiß das allerdings noch nicht (woher auch?).

Da der Bubblesort-Algorithmus keine Ahnung davon hat, dass die Zahlen bereits sortiert sind, führt er im ersten Durchlauf N-1 Vergleiche durch. Bei einem Array, der aus sechs Zahlen besteht, wird er also fünf Vergleiche durchführen.

Austauschoperationen müssen nicht durchgeführt werden, da es bei einem sortieren Array nichts auszutauschen gibt.

Also besteht der Rechenaufwand nur aus den 5 + 4 + 3 + 2 + 1 = 15 Vergleichen.

Worst-Case

Im denkbar ungünstigsten Fall sind die Zahlen ebenfalls sortiert, allerdings steht die größte Zahl vorne, gefolgt von der zweitgrößten und so weiter.

Auch hier kommt der Bubblesort bei sechs Zahlen mit 15 Vergleichen aus, genauso wie im Best-Case-Fall. Allerdings müssen die Zahlen nach jedem Vergleich vertauscht werden, also kommen 15 Tauschoperationen bzw. 45 Rechenoperationen hinzu (jeder Tausch besteht ja aus drei Schritten). Insgesamt sind wir für sechs Zahlen also bei 60 Rechenoperationen.

Normal-Case

Im Normalfall ist der Array weder aufsteigend noch absteigend sortiert, sondern die Zahlen sind nach dem Zufallsprinzip organisiert. Wie oft jetzt getauscht werden muss, kann man nur grob abschätzen. Vielleicht im Schnitt bei jedem zweiten Vergleich?

In diesem Fall hätten wir bei sechs Zahlen 15 Vergleiche und 7 oder 8 Tauschoperationen, also 36 oder 39 Rechenoperationen.

Herleitung einer Formel

Wie könnte man nun eine Formel für die Berechnung der Rechenoperationen beim Bubblesort herleiten? Betrachten Sie dazu die folgende Abbildung:

Die Zahl der Vergleiche ergibt sich nach der (hoffentlich) aus der Mathematik bekannten Formel für Summen der Art 1 + 2 + 3 + ... + N.

Für N = 6 ergibt sich daraus der Wert 15, was wir ja auch schon bei unseren Beispielen weiter oben festgestellt hatten.

Wenn wir den Best-Case und den Worst-Case-Fall einmal vernachlässigen, nehmen wir an, dass bei jedem zweiten Vergleich getauscht werden muss. Die Zahl der Tauschvorgänge, der "Austausche", liegt dann bei der Hälfte der Zahl der Vergleiche. Für die Zahl der Rechenoperationen muss allerdings die Zahl der Austausche mit drei multipliziert werden (drei Zuweisungen pro Austausch).

So erklärt sich dann die Formel für die Zahl der Rechenoperationen unten im Bild. Für N = 6 kämen wir damit auf 37,5 Rechenschritte. Das ist genau der Mittelwert zwischem dem Best-Case- und dem Worst-Case-Fall.

Ich persönlich bin leider ein Skeptiker und Naturwissenschaftler, weniger Mathematiker. Ich muss solche Formeln immer experimentell-praktisch überprüfen, und daher habe ich mir mal die Arbeit gemacht, für sechs Zahlen die Rechenoperationen Schritt für Schritt zu ermitteln.

Hier der erste Versuch:

Die ermittelte Zahl der Operationen liegt deutlich über dem Ergebnis der Formel!

Na ja, kann mal passieren. Also habe ich einen zweiten Versuch mit etwas anderen Zahlen laufen lassen:

Hier liegt die Zahl der Operationen etwas unter der berechneten Zahl. Dies ist jetzt natürlich noch kein Beweis dafür, dass die oben aufgestellte Formel stimmt, aber mir persönlich reicht es als Bestätigung aus.

Aber man soll ja immer kritisch sein, also dachte ich mir, recherchier' doch mal im Internet zum Thema "Zeitverhalten des Bubblesort", wobei mir gleich von Google vorgeschlagen wurde, ob ich nicht lieber nach "Bubbelsort" suchen wolle. So viel dazu. Dann habe ich mich doch etwas erschreckt, als ich die Suchergebnisse sah:

Eigentlich wollte ich auf anderen Seiten suchen und nicht dauernd auf meinen eigenen...

Toll! Auf der ersten Seite (www.hib-wien.at) steht überhaupt keine Formel, meine eigenen Seiten kenne ich schon (zumindest oberflächlich), die nächste Fundstelle gehört zu einem Forum, wo dem Fragesteller auch nicht weitergeholfen werden konnte, die nächste Fundstelle ist eine geklaute Kopie meiner eigenen Homepage! Vielleicht sollte ich den Leuten mal eine Abmahnung schicken, andererseits fühlt man sich natürlich geschmeichelt, wenn die eigenen Seiten so gut sind, dass sie geklaut werden. Auf der nächsten Seite geht es auch nicht um das Zeitverhalten, und so weiter. Ich habe jetzt keine Lust mehr, im Internet zu suchen. Wozu gibt es gute Fachbücher?

Dann will ich mal gleich in die Vollen gehen und in die "Bibel" der Algorithmik gucken: "The Art of Computer Programming" von Donald E. KNUTH, Volume 3 "Sorting und Searching", Second Edition. Auf Seite 109 findet man für die Zahl der Vergleiche die Formel 1/2 (N² - N). Genau die gleiche Formel also wie unser "Musterschüler" weiter oben entwickelt hat. Also Leute, ganz ehrlich - ich habe vorher nicht in den KNUTH geguckt sondern die Formel selbst hergeleitet - was ja auch nicht so besonders schwer ist.

Für die Zahl der Austauschoperationen findet KNUTH die Formel

min = 0

ave = 1/4 (N² - N)

max = 1/2 (N² - N)

Das entspricht völlig den bereits oben angestellten Überlegungen.

Zurück zur Folge 8

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 3. Oktober 2006 und von Grund auf erneuert am 21. Mai 2011 - Speziell für den 10er Kurs von Herrn Brennemann, der zur Zeit von Herrn Dölling vertreten wird. Ich hoffe, liebe Schüler (sind auch Mädchen im Kurs?), dass ich euch damit etwas weiterhelfen konnte. Neulich, als ihr mich während der Internet-AG angesprochen hattet, konnte ich mit euren Fragen ja nicht so viel anfangen, weil ich das Thema seit Oktober 2006 selbst nicht mehr bearbeitet hatte.