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 braucht daher keinen zusätzlichen Speicher. 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 in diversen Programmiersprachen
procedure bubblesort (A: in out Vektor) is
weiter:boolean:=true;
tmp:integer;
begin
while weiter loop
weiter:=false;
for i in 1..n-1 loop
if A(i)>A(i+1) then
weiter:=true;
tmp:=A(i);
A(i):=A(i+1);
A(i+1):=tmp;
end if;
end loop;
end loop;
end;
function 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
}
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 i;
for (i = 1; i <= N-1; i++)
{
int j;
for (j = 0; j < N-i; j++)
{
if (ptr[j] > ptr[j+1])
{
int temp;
temp = ptr[j];
ptr[j] = ptr[j+1];
ptr[j+1] = temp;
}
}
}
}
procedure TFrmTestprogramm.BubbleSort;
var ogrenz,i,zwischen:integer;
begin
for ogrenz := n downto 2 do
for i := 1 to ogrenz-1 do
if a[i] > a[i+1] then
begin
inc(vergleiche);
zwischen := a[i];
a[i] := a[i+1];
a[i+1] := zwischen;
inc(verschiebungen,3);
end;
end;
Die Pascal-Implementation funktioniert ebenfalls unter Delphi.
bSort :: (Ord a) => [a] -> [a]
bSort l = bSortA True [] l
bSortA :: (Ord a) => Bool -> [a] -> [a] -> [a]
bSortA False l [] = reverse l
bSortA True l [] = bSortA False [] (reverse l)
bSortA b [] (y:ys) = bSortA b [y] ys
bSortA b (x:xs) (y:ys)
| y < x = bSortA True (x:y:xs) ys
| otherwise = bSortA b (y:x:xs) ys
public class BubbleSort {
public static void sort(int[] array) {
// Wir nehmen erstmal an, dass das Array sortiert ist.
boolean sortiert = true;
do {
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.
final 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]);
}
}
}
procedure bubblesort(var f: Array of Integer);
var i,j,temp: Integer;
begin
for i:=High(f) downto Low(f)+1 do
for j:=Low(f)+1 to i do
if f[j-1] > f[j] then begin
temp := f[j-1];
f[j-1] := f[j];
f[j] := temp;
end;
end;
Die an die Funktion übergebenen Argumente werden in-place(in situ) sortiert.
sub bubblesort {
for my $i (0 .. $#_-1) {
for my $j (0 .. $#_-1-$i) {
if ($_[$j] > $_[$j+1]) {
($_[$j], $_[$j+1]) = ($_[$j+1], $_[$j]);
}
}
}
}
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;
}
bubbleSort(Unsortiert, Sortiert) :-
findePaar(Unsortiert, EtwasSortiert),
!,
bubbleSort(EtwasSortiert, Sortiert).
bubbleSort(Sortiert, Sortiert).
findePaar([Max,Min|Rest],[Min,Max|Rest]) :- Max >= Min,!.
findePaar([Erstes|Unsortiert],[Erstes|EtwasSortiert]) :-
findePaar(Unsortiert, EtwasSortiert).
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
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
(define bubble
(lambda (l)
(let ((s (bubble_once l)))
(if (sorted? s)
s
(bubble s)
))))
(define bubble_once
(lambda (l)
(cond
((empty? l) '())
((empty? (cdr l)) l)
((< (car l) (cadr l)) (cons (cadr l) (cons (car l) (bubble (cddr l)))))
(else (cons (car l) (bubble (cdr l))))
)))
(define sorted?
(lambda (l)
(cond
((empty? l) #t)
((empty? (cdr l)) #t)
(else (if (< (car l) (cadr l))
#f
(sorted? (cdr l))))
)))
!SequenceableCollection methodsFor: 'sorting' !
bubbleSort
| sorted |
[sorted := true. (1 to: self size - 1)
do: [:i | (self at: i + 1)< (self at: i)
ifTrue: [self swap: i with: i + 1. sorted := false]].
sorted] whileFalse! !
Beispielaufruf: #(1 2 3 4) shuffled bubbleSort → #(1 2 3 4) .
Die übergebene Liste wird sortiert und zurückgegeben. Hinweis: Die
eingebaute Funktion lsort kann das natürlich viel besser
und einfacher. Das Arbeiten mit der lindex-Funktion
ist nicht sehr elegant.
proc bubblesort {liste} {
set len_1 [expr [llength $liste] - 1]
for {set i 0} {$i < $len_1} {incr i} {
for {set j 0} {$j < [expr $len_1 - $i]} {incr j} {
if {[lindex $liste $j] > [lindex $liste [expr $j + 1]]} {
set tmp [lindex $liste $j]
lset liste $j [lindex $liste [expr $j + 1]]
lset liste [expr $j + 1] $tmp
} ;# if
} ;# for j
} ;# for i
return $liste
} ;# proc bubblesort
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.
2. Anm.: Das .NET-Äquivalent wäre n=a.length-1, UBound geht aber genauso gut. Im übrigen muss die For to Schleife von For i=0 To n-2 geändert werden.
Sub BubbleSort()
Dim i As Long, n As Long, Temp As Long
Dim Sortiert As Boolean
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 = 0 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
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)
- Java-Applet und Code zur Visualisierung
- 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