Sortieren durch Aufsteigen / Bubblesort
Die Grundidee
Die folgende Abbildung verdeutlicht die Grundidee eines Sortierverfahrens, das "Sortieren durch Aufsteigen" oder "Bubblesort" genannt wird.
Aufgabe 1
(a) Welche Elemente werden hier jeweils verglichen und ggf. vertauscht? Nach welcher Strategie werden die Vergleiche und Vertauschungen durchgeführt? Welche Bedeutung hat der blau unterlegte Bereich? Beschreibe die Grundidee des Verfahrens in Worten. Erkläre auch die Bezeichnung "Sortieren durch Aufsteigen": Was steigt hier auf?
(b) Führe das Sortierverfahren Sortieren durch Aufsteigen
am folgenden Beispiel durch.
Dokumentiere alle Zwischenschritte.
[25 17 15 56 19 66 8 20]
^ ^
[17 25 15 56 19 66 8 20]
^ ^
[17 15 25 56 19 66 8 20]
^ ^
[17 15 25 56 19 66 8 20]
^ ^
[17 15 25 19 56 66 8 20]
^ ^
[17 15 25 19 56 66 8 20]
^ ^
[17 15 25 19 56 8 66 20]
^ ^
[17 15 25 19 56 8 20 |66]
^ ^
...
(c) Kannst du die folgende Bubblesort-Animation erklären? Da sie sehr schnell abläuft, reicht es, wenn du dich auf den sortierten Bereich konzentrierst.
Ablaufmodellierung
Der folgende Sortierablauf soll jetzt präzisiert werden.
[25 17 32 56 25 19 8 66 29 6 20 29]
^ ^
[17 25 32 56 25 19 8 66 29 6 20 29]
^ ^
[17 25 32 56 25 19 8 66 29 6 20 29]
^ ^
...
[17 25 32 25 19 8 56 29 6 20 66 29]
^ ^
[17 25 32 25 19 8 56 29 6 20 29 |66]
^ ^
...
[17 25 25 19 8 32 29 6 20 56 29 |66]
^ ^
[17 25 25 19 8 32 29 6 20 29 |56 66]
^ ^
...
Informell lässt sich dieser Sortierablauf so beschreiben:
ALGORITHMUS bubblesort
Übergabe: Liste
unsortierter Bereich ist zunächst die gesamte Liste
SOLANGE der unsortierte Bereich noch mehr als ein Element hat:
durchlaufe den unsortierten Bereich von links nach rechts
wenn dabei zwei benachbarte Elemente in der falschen Reihenfolge vorliegen:
vertausche die beiden Elemente
verkürze den unsortierten Bereich durch Weglassen des letzten Elements
Rückgabe: überarbeitete Liste
Aufgabe 2
Entwickle ein Struktogramm zur Präzisierung des Ablaufs.
Aufgabe 3
Implementiere den Algorithmus bubblesort und teste das Sortierverfahren.
