Bubble-Sort als Volkstanz

erschienen in der Kategorie Software, am 28.08.2012
Schnatterente
Zu den wichtigsten Grundlagen der Informatik gehören zweifelsohne Sortieralgorithmen. Ein solches Verfahren nennt sich Bubblesort. Zwar wird Bubblesort in der Praxis kaum eingesetzt, da andere Verfahren weit effektiver arbeiten, doch kennen sollte man es als Informatiker schon.

In Ungarn dachte man sich wohl, dass es auf Dauer etwas öde ist, sich alles aus Büchern erarbeiten zu müssen, darum wird dort jetzt Bubblesort getanzt.



Na wenn das nicht mal nerdy ist, weiß ich's auch nicht.

Wem Bubblesort nach dem Schauen dieses Videos noch nicht einleuchtet, dem sei das Vorgehen kurz erklärt:

Wir sehen eine Reihe von Zahlen, die aufsteigend sortiert werden soll. Schrittweise werden (im Video von Links nach Rechts) je zwei Zahlen miteinander verglichen. Ist die erste Zahl größer als die zweite, tauschen die beiden Zahlen ihre Position und die größere Zahl wird wieder mit dem nächsten Element verglichen. Ist man ganz rechts angekommen, geht es einfach wieder von vorn los, so lange, bis alle Zahlen in der richtigen Reihenfolge sind.

Im Detail betrachtet, ist zu beachten, dass die größte Zahl bereits nach dem ersten Durchlauf ganz rechts steht. Da diese also nicht noch einmal betrachtet werden muss, endet die zweite Bubble-Runde schon mit dem Vergleichen des vorletzten Elements. Dieses muss dann wiederum in der darauffolgenden Runde nicht mehr betrachtet werden. Somit muss mit jeder weiteren Runde ein Element weniger verglichen werden.

So, jetzt solltet ihr alle in der Lage sein mit einem Aufwand von O(n²) Zahlen zu sortieren. Und was das bedeutet, erklär ich euch ein andermal.

Geschnatter

4 Kommentare, selbst mitschnattern << < Seite 1/1 > >>
Harald, am 30.01.2013 um 12:04 Uhr
Mal ehrlich, mehr nerdy geht nicht oder?
Christian Eiblmeier, am 26.02.2014 um 12:30 Uhr
Das is mir viel zu männlich {} c=3
Mils, am 09.10.2015 um 09:25 Uhr
supa toll
b00n, am 21.04.2016 um 09:48 Uhr
Tanzen wir am Tag der offenen Tür! :)