Skip to main content


Zutaten: Zucker, Kakaomasse (50%), Milchzucker, Weizenmehl, Vollmilchpulver, Magermilchpulver, Butterreinfett, Sahnepulver, Butter (1,4%)
Kann Spuren von Analysis und Geometrie enthalten.

IV_12_bubble-sort-titel

Bubble Sort Party

Rike, Ben und die anderen vom Institut feiern ihre erste Party. Es gibt Musik, Sekt und Bier in einem Berliner Loft. Als alle ein Glas in der Hand halten, fällt Rike die Ästhetik der aufsteigenden Blasen auf.

Rike Ist das nicht wunderschön?

Ben Ja, das ist schön, das gefällt allen theoretischen Informatikern. Nach diesem Große-Blasen-steigen-nach-oben-Phänomen wurde ein Sortieralgorithmus benannt: Bubble Sort.

Rike Erklär mal, wie der geht!

Die Bubble Sort-Idee

Ben Gut! Du fängst mit N Zahlen an, von denen Du nicht viel weißt. Die Zahlen nennen wir mal K_j und deren Anordnung oder Plätze R_j. Jetzt gehst Du alle j Zahlen durch – von 1 bis N – und prüfst, ob

K_j\; < \;K_{j+1}

Wenn das der Fall ist, werden die Plätze getauscht

R_j\;  \leftrightarrow \;R_{j+1}

Das heißt, an der j+1-ten Stelle steht nun die (ehemals) j-te Zahl, sie wird jetzt die j+1-te Zahl. Hier schau Dir das am Beispiel an:

Ein Beispiel

j12345678910111213141516
Kj49085106901789276542155061677670

16 zufällige Zahlen nach Donald Knuth

IV_12_bubble_02_07
1. Durchgang beim Bubble Sort nach D. Knuth. Paarweises Vergleichen und Vertauschen.

 

Rike Nicht schlecht, die 90 ist nach oben gerutscht! Aber Du bist noch nicht fertig!

Ben Stimmt. Du siehst, die größte Zahl hat es nach oben geschafft, das ist die Bubble-Metapher. Jetzt brauchen wir nur noch N-1 Zahlen vergleichen. Wir fangen wieder von unten (j\;=\;1) an. Im 2. Durchgang werden zuerst die 49 und die 6 getauscht, dann die 51 und die 17 und dann steigt die 89 nach oben.

IV_12_bubble_01_07
9 Durchgänge für das Donald-Knuth-Beispiel im Bubble Sort. Links der Anfang, rechts das Ergebnis. Abb. nach D. Knuth.

 

Rike Gefällt mir.

Ben Außerdem solltest Du überprüfen, ob Du fertig bist und nicht endlos die sortierte Reihe immer wieder überprüfen und endlich mal Dein Glas austrinken.

Fazit

Rike Klar, gute Idee. Sag mal, dann hast Du insgesamt höchstens N solche Durchgänge und in jedem Durchgang maximal N Vergleiche? Sind das nicht etwas zu viele Vergleiche, N^2? Du prüfst in jedem Durchlauf die unteren Zahlen erneut.

Ben Stimmt. Deshalb lieben ja nur die theoretischen Informatiker den Bubble Sort! Hahaha!

***

Übungsaufgabe

Schreibe ein Flow Chart für den Bubble Sort!

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Wir freuen uns, dass Du einen Kommentar hinterlassen möchtest. Denk bitte daran, dass Du dich durch das Abschicken des Kommentars mit unseren Nutzungsbedingungen einverstanden erklärst.