bullhost.de - PC Lexikon

Definition bzw. Erklärung: Bubblesort

[wörtlich: blasenartige Sortierung; ähnlich: ShakerSort, CoktailSort]

Bei dem EDV Begriff Bubblesort handelt es sich um einen einfachen Sortieralgorithmus von Daten. Der Algorithmus von Bubblesort basiert darauf, dass in mehreren Durchgängen das jeweils größte bzw. kleinste Element des gesamten Datenbestands ermittelt und entfernt wird. Beim Entfernen wird das entfernte Element an eine separat geführte Ergebnisliste angehängt. Es sind so viele Durchläufe notwendig wie sich Daten im Datenbestand befinden. Jedes einzelne Element des Datenbestands muss auf seine Gewichtung (kleiner oder größer) geprüft werden. Wenn es kleiner bzw. größer als das vorhergehende Element ist, werden die Elemente bei jedem Durchgang miteinander vertauscht. Durch dieses Vertauschen wandert das größere bzw. kleinere Element eine Position im Datenbestand nach oben. Nachdem schrittweise alle größten bzw. kleinsten Elemente bis zum letzten Element entfernt, vertauscht und an die separat geführte Ergebnisliste angefügt wurden, bildet die Ergebnisliste die sortierte Reihenfolge der einzelnen Elemente.

Der Terminus Bubblesort entstand durch die Eigenschaft von aufsteigenden Blasen in einem mit Sprudelwasser gefülltem Gals (englisch: Bubble = Blasen). Da das größte bzw. kleinste Element solange aufsteigt bis es an ein größeres bzw. kleineres Element stößt. Zu beachten gilt das dieser Sortieralgorithmus nur bei kleineren Datenmengen effektiv arbeitet (bis 50 Elemente), da die Worst-Case-Laufzeit exponential (quadratisch, O(n²)) zur Anzahl der Elemente steigt. Sollte man mehr als 50 Elemente sortieren wollen, so empfiehlt sich die Verwendung der Sortieralgorithmen Heapsort, MergeSort oder Quicksort, die im Vergleich zum Bubblesort bei größeren Datenmengen wesentlich schneller sortieren.

Alle Texte, Grafiken sowie das Design sind urheberrechtlich geschützt und dürfen nicht ohne Zustimmung von Bullhost Internet Service weiter verwendet werden.