Bubblesort
Der Begriff Blasensortierung oder oft englisch Bubblesort bezeichnet einen einfachen, stabilen Sortieralgorithmus, der eine Reihe linear angeordneter Elemente (z.B. Zahlen) der Größe nach anordnet.
Prinzip
Der Algorithmus vergleicht der Reihe nach zwei benachbarte Elemente und vertauscht sie, falls sie in der falschen Reihenfolge vorliegen. Dieser Vorgang wird solange wiederholt, bis keine Vertauschungen mehr nötig sind. Hierzu sind in der Regel mehrere Durchläufe erforderlich.
Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, d.h. an das Ende der Reihe. Auch werden immer zwei Zahlen miteinander in "Bubbles" vertauscht.
Komplexität
Der Algorithmus besitzt eine quadratische und daher im Vergleich zu vielen anderen Sortieralgorithmen schlechte Worst-Case-Laufzeit, die jedoch in der einfachen Version gleichzeitig auch der normalen Laufzeit entspricht, in der Informatik drückt man dies mittels Landau-Symbol durch O(n2) aus. Jedoch bietet dieser Algorithmus den Vorteil eines geringen Speicherbedarfes, da der Algorithmus ein In-place-Verfahren ist und anders als z.B. Quicksort keinen zusätzlichen Speicher belegt. Insgesamt hat der Algorithmus eine schlechte Zeitkomplexität, was durch eine sehr gute Platzkomplexität ausgeglichen wird.
Beispiel
Eine Reihe von 5 Zahlen soll aufsteigend sortiert werden.
Die fett gedruckten Zahlen werden jeweils verglichen. Ist die linke größer als die rechte, so werden beide vertauscht; das Zahlenpaar ist dann blau markiert.
55 07 78 12 42 1.Durchlauf 07 55 78 12 42 07 55 78 12 42 07 55 12 78 42 07 55 12 42 78 2.Durchlauf 07 55 12 42 78 07 12 55 42 78 07 12 42 55 78 3.Durchlauf 07 12 42 55 78 07 12 42 55 78 4.Durchlauf 07 12 42 55 78 Fertig sortiert.
Formaler Algorithmus
Im Folgenden sei die zu sortierende Datenreihe mit x bezeichnet. Sie enthält N Elemente, die von 1 bis N indiziert seien, d.h. x[1], ..., x[N]. Es ist wichtig, die Schleifengrenzen korrekt zu wählen.
Schleife über Durchlauf = 1 .. N-1
{
Schleife über Position = 1 .. N-Durchlauf
{
Falls x[Position] > x[Position+1] ...
{
... dann Vertausche x[Position] und x[Position+1]
}
}
}
Implementierungen
Die N Elemente liegen in einem Feld vor (Index von 0...N-1) ptr enthält die Adresse des ersten Feldelementes (Index 0).
void bubblesort(int *ptr, int N)
{
int temp;
for (int i=0; i<N-1; i++)
{
for (int j=0; j < N-1-i; j++)
{
if ( ptr[j] > ptr[j+1] )
{
temp = ptr[j];
ptr[j] = ptr[j+1];
ptr[j+1] = temp;
}
}
}
}
procedure BubbleSort(var AArray : array of LongInt);
var
Done : Boolean;
Index : LongInt;
Rounds : LongInt;
Temp : LongInt;
begin
Done := false;
Rounds := 0;
while not(Done) do
begin
Done := true;
for Index := Low(AArray) to Pred(High(AArray) - Rounds) do
begin
if (AArray[Index] > AArray[Succ(Index)]) then
begin
Done := false;
Temp := AArray[Index];
AArray[Index] := AArray[Succ(Index)];
AArray[Succ(Index)] := Temp;
end;
end;
Inc(Rounds);
end;
end;
Die unsortierten Zahlen (32 Bit, ganzzahlig) liegen im Feld a (Index beginnt bei 0), die Feldgröße wird dynamisch ermittelt. Die Variablen i und j fungieren als Zählvariablen, n speichert die Feldgröße und t dient als temporärer Speicher beim Vertauschen.
Anm.: Dieser Code wurde für Visual Basic bis Version 6 geschrieben, kann aber auch für Visual Basic .NET verwendet werden, wenn die UBound-Funktion durch ihr .NET-Äquivalent ersetzt wird.
Sub BubbleSort()
Dim i As Long, n As Long, Temp As Long
n = UBound(a) 'Feldgröße bestimmen
Do
'In diesem Durchgang wurden noch keine Veränderungen vorgenommen
Sortiert = True
'Gehe alle Feldelemente durch außer dem letzten
For i = 1 To n - 1
'Vergleiche das aktuelle Feldelement mit dem nächsten
If a(i) > a(i + 1) Then
'Ist dieses größer, vertausche die beiden Werte
Temp = a(i)
a(i) = a(i + 1)
a(i + 1) = Temp
'Es wurden Veränderungen vorgenommen
Sortiert = False
End If
Next i
'Wiederhole den Vorgang, bis bei einem Durchgang keine Veränderungen vorgenommen werden mussten
Loop Until Sortiert
End Sub
public class BubbleSort {
public static void sort(int[] array) {
boolean sortiert;
do {
// Wir nehmen erstmal an, dass das Array sortiert ist.
sortiert = true;
// Nun gehen wir das Array komplett durch...
for (int i = 1; i < array.length; i++) {
// und vergleichen jedes Element mit dem linken Nachbar,
// darum fängt die for-Schleife auch mit 1 an und nicht mit 0.
if (array[i - 1] > array[i]) {
// Sollte das linke Element größer sein als das rechte, so werden diese beiden vertauscht.
int tmp = array[i - 1];
array[i - 1] = array[i];
array[i] = tmp;
// Und wir merken uns, dass das Array eben doch nicht sortiert war.
sortiert = false;
}
}
// Den obigen Code müssen wir nun so lange ausführen, bis keine Vertauschungen mehr nötig sind.
// Dies ist genau dann der Fall, wenn das array sortiert ist.
} while (!sortiert);
// Diese Methode braucht auch keinen Rückgabewert, da das übergebene Array modifiziert wird.
}
// nur zum Testen
public static void main(String[] args) {
int[] test = {52,654,15,994,2,35,12,5,7,9};
sort(test);
for (int i=0; i<test.length; i++) {
System.out.println(test[i]);
}
}
}
def bubble_sort!(feld)
for i in 1..feld.length
for j in 0..(feld.length-1-i)
if feld[j] > feld[j+1] then
feld[j], feld[j+1] = feld[j+1], feld[j]
end
end
end
return feld
end
def bubble_sort(lst):
for i in range(0, len(lst)):
for j in range(0, len(lst) - 1 - i):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
return lst
function bubblesort($array)
{
$anzahl = count($array);
for($i = 0; $i < $anzahl; $i++)
{
for($j = 0; $j <= $anzahl - $i - 2; $j++)
{
if($array[$j] > $array[$j+1])
{
$a = $array[$j];
$array[$j] = $array[$j+1];
$array[$j+1] = $a;
}
}
}
return $array;
}
Die an die Funktion übergebenen Argumente werden in-place sortiert.
sub bubblesort {
for my $i (0 .. $#_-1) {
for my $j (0 .. $#_-1-$i) {
if ($_[$j] > $_[$j+1]) {
($_[$j], $_[$j+1]) = ($_[$j+1], $_[$j]);
}
}
}
}
fuction SORT()
{
LIST=$1
SORTED=0
MAX_COUNT=0
for ELEMENT in $LIST; do
let MAX_COUNT=$MAX_COUNT+1
done
while [ $SORTED = 0 ] ; do
SORTED=1
for (( COUNTER=0 ; $((MAX_COUNT - COUNTER - 1)) ; COUNTER++ )) ; do
if [ "${LIST[$COUNTER]}" \> "${LIST[$COUNTER+1]}" ] ; then
SORTED=0
HELPER=${LIST[$COUNTER]}
LIST[$COUNTER]=${LIST[$COUNTER+1]}
LIST[$COUNTER+1]=$HELPER
fi
done
done
}
Varianten
Die Geschwindigkeit kann erhöht werden, indem man eine Abbruchbedingung einbaut, die die äußere Schleife beendet, falls bei einem Durchlauf der inneren Schleife keine Vertauschung stattgefunden hat, die Reihe also bereits sortiert ist. Diese Bubblesort-Variante ist für vorsortierte Arrays ziemlich schnell (d.h. auch schneller als einige andere Algorithmen). Die Aufwandsklasse bleibt allerdings weiterhin O(n2).
Manchmal wird der Bubblesort-Algorithmus modifiziert, indem die Richtung des Schleifendurchlaufs bei jeder Iteration geändert wird. Zunächst wird also von unten nach oben, danach von oben nach unten usw. gesucht, in der Hoffnung, dass die Bubbles dann schneller ihre Position erreichen. Der Algorithmus wird dann auch Shakersort oder Cocktailsort genannt. Die Hoffnung trügt allerdings, der neue Algorithmus ist theoretisch in keiner Hinsicht besser als Bubblesort, er ist nur ein wenig komplizierter. In der Praxis kann er aber dennoch schneller sein.
Siehe auch
Weblinks
- VisuSort Framework - Visualisierung diverser Sortieralgorithmen (Windows)
- http://olli.informatik.uni-oldenburg.de/fpsort/Animation.html - interaktive Animation des Verfahrens mit Codebeispielen
- http://www.inf.ethz.ch/~staerk/algorithms/SortAnimation.html - Java-Beispiele für Sortieralgorithmen
- http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Bubble_sort