Das Prinzip des BubbleSorts ist einfach. Im folgenden sind die einzelnen Schritte
des Algorithmus bei seiner Vorgehensweise niedergeschrieben.
Zu Begin des Ablaufs
wird eine Marke auf das letzte Element in der Datenmenge gesetzt. Der Wert dieser Marke
spiegelt den Fortschritt des Algorithmus. Nun wird die Datenmenge,
beginnend beim zweiten Element zur Marke hin, durchlaufen und das grösste Element so weit wie
möglich zur Marke geschoben. Nach einem Durchlauf wird die Marke um ein Element nach vorne gerückt
und ein neuer Durchlauf gestartet. Dies wiederholt sich so lange, bis die Marke das erste
Element erreicht hat, da kein weiterer Duchlauf möglich wäre.
Von hinten her bildet
sich in der Datenmenge ein sortiertes Feld. Dieses wird bei jedem Durchlauf um genau ein Element
grösser. Die dort eingereihten Elemente werden nicht mehr
untersucht, da sie beim nächsten Durchlauf hinter der Marke liegen.
Da von der Restmenge die grössten Elemente in den sortierten Teil der Menge 'verschwinden', erscheinen
und wandern die kleinen nach hinten. Jedoch kann nicht sichergestellt werden, dass sich auch von vorn ein
sortiertes Feld bildet. Dieses Verhalten implementiert aber der bidirektionale BubbleSort.
- Falls die Marke auf das erste Element zeigt, terminiert BubbleSort.
- Element an der aktuellen Position wird mit seinem Vorgänger verglichen.
- Falls der Vorgänger grösser ist als das aktuelle Element werden die beiden vertauscht.
- Nun wird um genau ein Element vorgerueckt. Sprich die aktuelle Position wird inkrementiert.
- Falls die aktuelle Position die Marke erreicht hat, wird die aktuelle Position wieder auf das zweite
Element gesetzt, die Marke um eins verringert und bei Punkt 1 weiter gemacht. Ansonsten wird die Ausführung bei
Punkt 2 fortgesetzt.
Nächste Seite
Aufwärts
Vorherige Seite
Inhalt
Nächste Seite: Beispiel
Aufwärts: Arbeitsweise
Vorherige Seite: Arbeitsweise
Inhalt
2002-05-09
