Sortieren durch Aufsteigen / Bubblesort

Eine Lego-Sortieranimation

Auf YouTube gibt es eines interessantes Video zum Sortieren: Lego-Bubblesort.

Aufgabe 1

Schaue dir das Video genau an. Wie gehen die Lego-Arbeiter beim Sortieren vor? Kannst du die Grundidee des benutzten Sortierverfahrens beschreiben?

Die Gundidee

Die folgende Abbildung verdeutlicht die Grundidee eines Sortierverfahrens, das "Sortieren durch Aufsteigen" oder "Bubblesort" genannt wird.

Aufgabe 2

(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:
    duchlaufe 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 3

Entwickle ein Struktogramm zur Präzisierung des Ablaufs.

Aufgabe 4

Implementiere den Algorithmus bubblesort und teste das Sortierverfahren.