BUBBLE SORT

Bubble Sort

 

[dt. »blasenartiges Sortieren«], ein einfacher Algorithmus für die Sortierung von Daten. Das Verfahren beruht darauf, dass die Elemente des Bestands mehrfach nacheinander durchgesehen werden, bei jedem Durchgang wird das größte bzw. kleinste Element entfernt und an die (sortierte) Ergebnisliste angehängt. Bei einem Durchgang werden jeweils zwei benachbarte Elemente verglichen und vertauscht, wenn sie nicht in der korrekten Reihenfolge stehen. Im Ergebnis eines Durchgangs steht das größte (kleinste) Element am Ende und kann entfernt werden. Wenn der unsortierte Rest nur noch aus einem Element besteht, ist die Sortierung beendet.

 

Stellt man den (unsortierten) Datenbestand in einer senkrechten Reihe dar, dann kann man das Verfahren mit dem Aufsteigen von Blasen (engl. bubbles) in einem Sprudelglas vergleichen: Große »Blasen« (d. h. zu sortierende Daten) steigen solange auf, bis sie durch eine noch größere Blase aufgehalten werden, die ihrerseits weiter aufsteigt.

 

Das Bubble-Sort-Verfahren eignet sich nur für kleine Datenbestände (max. 50 Elemente), da die Laufzeit quadratisch mit der Zahl der Elemente steigt. Schnellere Sortierverfahren sind z. B. Heap Sort oder Quick Sort.