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(n²) 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..., 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> x[Position+1 ... { ... dann Vertausche xund x[Position+1 } } }

Implementierungen

C

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> ptr[j+1 ) { temp = ptr^*; ptr= ptr[j+1; ptr^* = temp; } } } }

Pascal und Delphi

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> AArray[Succ(Index)) then begin Done := false; Temp := AArray^*; AArray := AArray[Succ(Index); AArray^* := Temp; end; end; Inc(Rounds); end; end;

Visual Basic

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

Java

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- 1 > array^*) { // Sollte das linke Element größer sein als das rechte, // so werden diese beiden vertauscht. int tmp = array- 1; array- 1 = array^*; array^* = 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^*); } } }

Ruby

def bubble_sort!(feld) for i in 1..feld.length for j in 0..(feld.length-1-i) if feld> feld[j+1 then feldfeld ^*," target="_blank" >feld[j end end end return feld end

Python

def bubble_sort(lst): for i in range(0, len(lst)): for j in range(0, len(lst) - 1 - i): if lst> lst[j + 1: lstlst + 1, lst[j" target="_blank" >^* return lst

PHP

function bubblesort($array) { $anzahl = count($array); for($i = 0; $i < $anzahl; $i++) { for($j = 0; $j <= $anzahl - $i - 2; $j++) { if($array> $array[$j+1) { $a = $array^*; $array= $array[$j+1; $array^* = $a; } } } return $array; }

Tcl

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 ^*
  for {set i 0} {$i < $len_1} {incr i} {
    for {set j 0} {$j < $len_1 - $i} {incr j} {
      if {$liste $j > $liste ^*} {
        set tmp $liste $j
        lset liste $j $liste ^*
        lset liste $j + 1 $tmp
      } ;# if
    } ;# for j
  } ;# for i
  return $liste
} ;# proc bubblesort

Perl

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+1) { ($_$_^*," target="_blank" >$_[$j); } } } }

Bash

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 "${LIST^*}"" target="_blank" > ; then
        SORTED=0
        HELPER=${LIST^*}
        LIST^*=${LIST^*}
        LIST^*=$HELPER
      fi
    done
  done
}

Haskell


bSort :: (Ord a) => -> [a
bSort l = bSortA True ^* l
bSortA :: (Ord a) => Bool -> -> ^*
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

Prolog


bubbleSort(Unsortiert, Sortiert) :-
                findePaar(Unsortiert, EtwasSortiert),
                !,
                bubbleSort(EtwasSortiert, Sortiert).
                
bubbleSort(Sortiert, Sortiert).
findePaar(^*,^*) :- Max >= Min,!.
findePaar(^*,^*) :-
                findePaar(Unsortiert, EtwasSortiert).

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(n²).

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

Liste von Algorithmen

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

Sortieralgorithmus

Gourt Home::Gourt :: Bubblesort