Bubble sort

= Sortieren durch direktes Austauschenr />

Laufzeit:
Bubble Sort benötigt im Durchschnitt und im ungünstigsten Fall ungefähr n²/2 Vergleiche und n²/2 Austauschoperationen.

Funktionsweise:
Hier wird die Datei immer wieder durchlaufen und wenn das maximale Element gefunden wird, wird es mit jedem rechts von ihm stehenden Element getauscht; solange, bis es das rechte Ende des Feldes erreicht hat.




Beschreibung:
1. Durchgang:
In der 1. Zeile wird der 8er mit dem 5er verglichen und da sie nicht in der Reihenfolge stehen, werden sie vertauscht.
In der 2. Zeile wird der 8er mit dem 9er verglichen, da sie in gleicher Reihenfolge stehen, wird kein Tauschvorgang vorgenommen.
In der 3. Zeile wird der 9er mit dem 7er verglichen und vertauscht.
In der 4. Zeile wird der 9er mit dem 1er verglichen und vertauscht.
In der 5. Zeile wird der 9er mit dem 6er verglichen und vertauscht.
In der 6. Zeile wird der 9er mit dem 3er verglichen und vertauscht.
In der 7.Zeile steht nun das größte Element (=9) an letzter Stelle, aber von sortierten Zahlen ist noch keine Rede. Es wird daher noch ein Durchgang benötigt. Es müssen allerdings nur mehr 6 Elemente statt 7 Elemente durchsucht werden.


2. Durchgang:
Beim 2. Durchgang wird ganz genauso vorgegangen wie beim 1., bis wieder das größte Element an letzter bzw. an vorletzter Stelle steht, also vor dem 9er.
Bis jedoch das gesamte Feld sortiert ist, sind noch ein paar Durchgänge notwendig.
Wie man sieht, wandert immer das größte Element nach hinten. Dadurch sind nach jedem Durchgang nur mehr N-1 Elemente zu durchsuchen.
Das ist der große Vorteil des Bubble Sort.

Um den Vergleich der Methoden weiterzuführen, ist es erforderlich, die Kosten von Vergleichs- und Austauschoperationen zu analysieren, ein Faktor, der wiederum von der Größe der Datensätze und Schlüssel abhängt. Wenn zum Beispiel die Datensätze, wie in den obigen Implementationen, aus einem Wort bestehende Schlüssel sind, so dürfte ein Austausch (zwei Zugriffe auf das Feld) etwa doppelt so teuer sein wie ein Vergleich. In einer solchen Situation sind die Laufzeiten von Selection Sort und Insertion Sort grob gesagt, vergleichbar, während Bubble Sort doppelt so viel Zeit benötigt. (Tatsächlich dürfte Bubble Sort unter nahezu allen Umständen halb so schnell sein wie Insertion Sort!) Falls jedoch die Datensätze im Vergleich zu den Schlüsseln groß sind, ist der Selection Sort am besten geeignet.