|
BubbleSort zählt zu
den Elementaren Sortierverfahren und ist im weitesten Sinne eine
Fortentwicklung von InsertionSort.
BubbleSort verfährt nach folgender Methode:
Man durchläuft die Liste a[1]...a[N] der Datensätze und betrachtet dabei
je zwei benachbarte Elemente a[i] und a[i+1]. Ist
a[i].key > a[i+1].key, so vertauscht man a[i] und a[i+1]. Das Durchlaufen des Arrays wird solange wiederholt, bis keine Elemente
mehr vertauscht wurden, das Array also sortiert ist.
Das Verfahren hat seinen Namen, da größere Elemente wie Luftblasen
nach oben/rechts aufsteigen.
Bsp.:
Feld B =
15,2,43,17,4,8,47
Nach
1. Durchlauf:
2,15,17,4,8,43,47
Nach
2. Durchlauf:
2,15,4,8,17,43,47
Nach
3. Durchlauf:
2,4,8,15,17,43,47
Keine
Vertauschungen mehr bei 4. Durchlauf à Feld Sortiert
Analyse:
à O(n²)
Warum:
Ist das Feld absteigend sortiert, so muss das erste Element n
Schritte bewegt werden, das zweite Element (n-1), das n. Element 1
Schritt bewegt werden.
à Es sind [n + (n-1) +(n-2) + ... + 1 ]* c = [c*n*(n-1)] / 2
Schritte notwendig.(c=const.)
à
[c*n*(n-1)] / 2 Є O(n²)
-
AveragCase O(n²)
-
BestCase O(n)
-
Iterativer Algorithmus
-
In-Place
|
