i

Sortieren durch Aufsteigen / Bubblesort

Die Grundidee

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

Bubblesort

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.

Suche

v
2.4.1.1.3
dev.inf-schule.de/algorithmen/komplexitaet/sortieren/sortieralgorithmen/bubblesort
dev.inf-schule.de/2.4.1.1.3
dev.inf-schule.de/@/page/S4HrZ1ckp4Hg6jsP

Rückmeldung geben