BubbleSort

Auf digitalen Geräten (Smartphone, Computer, etc.) sucht man ständig etwas: Eine App, einen Song, ein Video. Auch auf Webseiten und innerhalb von Apps ist man ständig auf der Suche. Denken Sie nur mal daran, was Sie als erstes tun, nachdem Sie die Amazon-Webseite geöffnet haben.

So eine Suche kann aber nur dann schnell gehen, wenn die Daten, die man durchsucht, sortiert sind! Denken Sie nur an die Lottozahlen - wenn die Liste sortiert ist, finden Sie ihre Zahlen schneller.

Nicht nur Menschen, sondern auch Computer finden das Gesuchte in sortierten Daten wesentlich schneller. Wir werden uns deshalb anschauen, wie man man das hinkriegt: Wir sortieren Daten!

BubbleSort - Leicht zu verstehen!

In der Praxis verbringen viele Computer einen Großteil ihrer Zeit damit, Daten zu sortieren. Weil das Sortieren so wichtig ist, hat man viele verschieden Algorithmen (also klar definierte Vorgehensweisen) erfunden, um dieses Ziel zu erreichen. Wir schauen uns jetzt einen Sortier-Algorithmus an, der ziemlich leicht zu verstehen ist: Bubble Sort.

(Kleine Vorbemerkung zur Schreibung: BubbleSort und Bubble Sort, beides kommt vor, wobei man im Deutschen meistens Bubblesort schreibt.)

Der Größte-Zahl-ans-Ende-Algorithmus

• Wir fangen links an und vergleichen zwei benachbarte Elemente des Arrays.
• Wenn das linke Element größer ist als das rechte, dann "wandert es nach rechts", es wird also getauscht.
• Nachdem wir so alle benachbarten Elemente des Arrays verglichen haben, steht das größte Element am Ende des Arrays!

Beispiel: Ein Array mit 4 Zahlen

Wie oft muss verglichen werden?

Wir sehen, dass wir bei 4 Zahlen genau 3 Vergleiche benötigen. Daraus können wir diese Erkenntnis gewinnen:

Anzahl Vergleiche = Länge des Arrays - 1

Struktogramm: Größte-Zahl-ans-Ende-Algorithmus

Aufgabe zum »Größte Zahl ans Ende«-Algorithmus

BubbleSort: Mehrere Durchgänge

Unser Ziel ist es, das komplette Array zu sortieren. Genau das kriegen wir hin, wenn wir den Größte-Zahl-ans-Ende-Algorithmus in mehreren Durchgängen auf das restliche Array anwenden. Schauen wir uns das im Beispiel an:

Damit haben wir es fast geschafft: Noch ein weiterer Durchgang mit dem Größte-Zahl-ans-Ende-Algorithmus:

Bubble Sort: Wie viele Durchgänge brauchen wir?

Sie sehen: Wenn wir unseren Größte-Zahl-ans-Ende-Algorithmus mehrmals anwenden, haben wir am Schluss ein komplett sortiertes Array!

Die Frage ist jetzt: Wie viele Durchgänge brauchen wir, bis das Array sortiert ist?

Wir müssen also das Folgende tun, um ein Array mit BubbleSort zu sortieren:

Der Teil, der wiederholt werden soll, muss also ebenfalls in eine Schleife verschoben werden:

Betrachten wir nochmal, welche Elemente wir in den einzelnen Durchgängen miteinander vergleichen:

Sie müssten sehen, dass die Schleife zum Vertauschen der Elemente jedes Mal kürzer läuft. Wir verändern unser Struktogramm entsprechend, um das zu berücksichtigen:

Aufgaben zum Sortieren mit BubbleSort

Erklärvideo: BubbleSort

Erklärvideo: BubbleSort im Struktogramm und Wertetabellen

Arbeitsblatt: BubbleSort (mit Aufgaben)

Arbeitsblatt »BubbleSort« (PDF)

Übungsblatt »BubbleSort - Vorlage zur Übung Namen sortieren« (docx)