Der Bubblesort ist ein leicht verständlicher, doch meistens ein ineffizienter (Zeitkomplexität O(n2)) Ansatz, Werte einer Liste anhand der Grössenordnungen zu sortieren.
In der Praxis kommt dieser selten zum Zug, höchstens bei Nischenanwendungen (bspw. eingebetteten Systeme) oder für akademische Zwecke, da er einfach zu verstehen ist.
Dennoch schneidet es unter bestimmten Umständen besser als andere Sortierungsalgorithmen ab und zwar bei fast vollständig sortierten Datensätze.
Er ist nicht grundsätzlich abzuraten, bei kleinen Datensätzen ist er geschwindigkeitsmässig akzeptabel, was ihn für einfache Szenarien geeignet macht.
Prozess
Genug davon herumgeredet, wie wird der Algorithmus angewendet?
An einem Ende der zu sortierende Liste, typischerweise links, wird ein sogenannter "Zeiger" gesetzt.
Dieser springt von einem Wert zum benachbarten.
Vor jedem Sprung dieses Zeigers wird der aktuelle Wert mit dem nächstliegenden verglichen.
Ist dieser kleiner als der Aktuelle, so werden sie getauscht.
Trifft der Zeiger aufs Ende, so wiederholt sich der Prozess ab dem 1. Eintrag, sofern Tauschungen im Durchgang stattgefunden haben.
Das war der reine Bubblesort. Eine gängige optimierte Version besteht darin, die Liste nach jedem Durchgang um den letzten Eintrag zu verkürzen. Da dieser nach einem vollständigen Durchgang garantiert an der richtigen Position steht, müssen weitere Vergleiche mit diesem Element nicht mehr durchgeführt werden.
Der Begriff bubblesort nimmt Inspiration vom blasenartigen "aufschwimmen" der grössten Werte.
Beispiel
Als Code
The following lines of code illustrate bubblesort in JavaScript:
function bubbleSort(list) {
for (let pendingListItems = list.length; pendingListItems > 0; pendingListItems--) {
for (let listIndex = 0; listIndex < pendingListItems - 1; listIndex++) {
if (list[listIndex] > list[listIndex + 1]) {
const tempItem = list[listIndex];
list[listIndex] = list[listIndex + 1];
list[listIndex + 1] = tempItem;
}
}
}
return list;
}
DE 
EN