Startseite
Informatik
Algorithmen
Sortieren
BucketSort
RadixSort
QuickSort
MergeSort
HeapSort
DRUCK
2004
2005
2006
2007
2008
2009
BubbleSort
ShakerSort
SelectionSort
InsertionSort
SlowSort
BogoSort
Komprimieren
Suchen
Primzahltest
Datenstrukturen
Software-Engineering
Programmiersprachen
Künstliche Intelligenz
Schach
Privates
Inhalt
BubbleSort
Ein äußerst ineffizienter Sortieralgorithmus ist der BubbleSort!
Ein äußerst ineffizienter Sortieralgorithmus ist der BubbleSort!
Einführung
Theorie: BubbleSort
Definition
BubbleSort
ist die Bezeichnung für ein einfaches Verfahren zum Sortieren eines linearen Feldes:
Beim Durchlaufen des Feldes vertauscht man zwei benachbarte Elemente, wenn sie nicht in der korrekten Reihenfolge stehen.
Schreibt man das Feld von unten nach oben auf, dann kann man das Verfahren mit dem
Aufsteigen von Blasen
(englisch: bubble)
in einem Sprudelglas vergleichen:
Größere Blasen
(Elemente des Feldes)
steigen solange auf, bis sie durch eine noch größere Blase aufgehalten werden, die ihrerseits weiter aufsteigt.
[INFODUDEN]
Komplexität
BubbleSort sollte nur für kleine Felder
(n < 30)
verwendet werden, da seine Laufzeit quadratisch von n abhängt, also die Ordnung
O(n²)
hat.
1
Schnellere Sortierverfahren sind zum Beispiel QuickSort und HeapSort. [INFODUDEN]
Es gibt auch schnellere Varianten des BubbleSort wie z. B. der ShakerSort oder der CompSort.
Schnellere Sortierverfahren sind zum Beispiel QuickSort und HeapSort. [INFODUDEN]
Es gibt auch schnellere Varianten des BubbleSort wie z. B. der ShakerSort oder der CompSort.
Beispiel: Sortieren von Spielkarten
Der Spieler nimmt alle Karten auf, macht eine
Hand
daraus und fängt jetzt an, die Hand zu sortieren, indem er benachbarte Karten solange vertauscht, bis alle in der richtigen
Reihenfolge liegen.
Dieser Algorithmus wird
BubbleSort
genannt.
[INFO2002]
Konkretes Zahlenbeispiel
Dabei sei nun
Der ShakerSort ist eine Verbesserung des Verfahrens dahingehend, dass er abwechselnd die größeren Zahlen aufsteigen und die kleineren Zahlen absinken lässt.
[6,2,4,7,3,5,1]
die zu sortierende Liste:
[6,2,4,7,3,5,1][2,4,6,3,5,1,7][2,4,3,5,1,6,7][2,3,4,1,5,6,7][2,3,1,4,5,6,7][2,1,3,4,5,6,7][1,2,3,4,5,6,7]
Der ShakerSort ist eine Verbesserung des Verfahrens dahingehend, dass er abwechselnd die größeren Zahlen aufsteigen und die kleineren Zahlen absinken lässt.
Implementierung
Implementierung des BubbleSort
Bei der Realisierung von BubbleSort verschachtelt man üblicherweise zwei Zählschleifen.
Die äußere Schleife geht höchstens einmal die gesamte Liste der zu sortierenden Elemente durch.
Die innere Schleife sollte aus Effizienzgründen
(Halbierung der Laufzeit)
mit der äußeren Zählschleife korrelieren
(hier: C-Code),
indem sie jedesmal vom aktuellen Element aus, den noch unsortierten Rest durchläuft;
2
die innere Schleife darf aber auch die gesamte Liste durchlaufen
(hier: Delphi-Code).
Das Aufsteigen der Blasen wird mit einer Swap-Funktion realisiert, d. h. eine Blase steigt auf, gleichzeitig sinkt eine andere Blase ab. Die Blasen, die bezüglich ihrer Größe verglichen und gegebenenfalls geswappt werden, sind generell benachbart.
Das Aufsteigen der Blasen wird mit einer Swap-Funktion realisiert, d. h. eine Blase steigt auf, gleichzeitig sinkt eine andere Blase ab. Die Blasen, die bezüglich ihrer Größe verglichen und gegebenenfalls geswappt werden, sind generell benachbart.
Implementierung mit Delphi
unit UBubbleSort;
interface
procedure BubbleSort(var A: array of Integer);
implementation
procedure BubbleSort(var A: array of Integer);
procedure Swap(var X, Y: Integer);
var
Swp: Integer;
begin
Swp := X;
X := Y;
Y := Swp;
end;
var
I, J: Integer;
begin
for I := Low(A) to High(A) do
for J := Low(A) to High(A) - 1 do
if A[J] > A[J + 1] then Swap(A[J], A[J + 1]);
end;
end.
Implementierung mit C++
#include <stdio.h>
#include <stdlib.h>
/* Sortiert (aufsteigend) die ersten n Elemente des int-Arrays v */
void bubblesort(int v[], int n) {
for (int i = n - 1; i > 0; i--) {
// innere Schleife abhängig von i (Korrelation)
for (int j = 0; j < i; j++) {
// ggf. Korrektur der Ordnung zweier,
// aufeinanderfolgender Werte
if (v[j] > v[j + 1]) {
// ein kleiner Bubble-Schritt (Vertauschung)
int swp = v[j];
v[j] = v[j + 1];
v[j + 1] = swp;
}
}
}
}
// Kleiner Test: Lass bubbeln!
int main() {
int values[] = {25, 13, 19, 31, 11, 99, 21, 17};
int count = sizeof(values) / sizeof(*values);
// Ausgabe der Werte (vorher)
for (int i = 0; i < count; i++) printf("%5d", values[i]);
printf("\n");
// Sortiere alle (count!) Elemente von values
bubblesort(values, count);
// Ausgabe der Werte (nachher)
for (int i = 0; i < count; i++) printf("%5d", values[i]);
printf("\n");
system("PAUSE");
return(0);
}
/* Ausgabe bei Ausführung des Programms:
* 25 13 19 31 11 99 21 17
* 11 13 17 19 21 25 31 99
*/
Implementierung mit Prolog
% ?-bubblesort([2, 1, 4, 7, 3, 5, 6], SL).
bubblesort([], []).
bubblesort(L, SL) :- bubbleup(L, ZL), !, bubblesort(ZL, SL).
bubblesort(SL, SL).
bubbleup([X, Y|L], [Y, X|L]) :- X > Y.
bubbleup([Z|L], [Z|ZL]) :- bubbleup(L, ZL).
Implementierung mit Perl
#!/usr/bin/perl
sub BubbleSort
{
my ($compare, @list) = @_;
foreach (@list)
{
for (my $i = 0; $i < $#list; $i++)
{
if (&$compare($list[$i + 1], $list[$i]))
{
($list[$i], $list[$i + 1]) = ($list[$i + 1], $list[$i]);
}
}
}
return @list;
};
# --- Anwendungsbeispiele ---
# Vergleichsfunktionen
my $asc = sub { return $_[0] < $_[1]; }; # für aufsteigende Sortierung
my $desc = sub { return $_[0] > $_[1]; }; # für absteigende Sortierung
@A = ( 4, 2, 9, 3, 0, 5, 1, 8, 6, 7 );
@B = BubbleSort($asc, @A);
@C = BubbleSort($desc, @A);
print "# @A (unsortiert)\n";
print "#\n";
print "# @B (aufsteigend; asc)\n";
print "# @C (absteigend; desc)\n";
# --- Besondere Anwendungsbeispiele ---
@X1 = ( 4, 2, 9, 3, 0 );
@X2 = ( 8, 6, 7 );
@X3 = ( 5, 1 );
@X = BubbleSort($asc, @X1, @X2, @X3);
@Y = BubbleSort($asc, 4, 2, 9, 5, 7, 6, 0, 1, 3, 8);
print "#\n";
print "# @X (3 Arrays sortiert)\n";
print "# @Y (Argumente sortiert)\n";
# --- Ausgabe ---
# 4 2 9 3 0 5 1 8 6 7 (unsortiert)
#
# 0 1 2 3 4 5 6 7 8 9 (aufsteigend; asc)
# 9 8 7 6 5 4 3 2 1 0 (absteigend; desc)
#
# 0 1 2 3 4 5 6 7 8 9 (3 Arrays sortiert)
# 0 1 2 3 4 5 6 7 8 9 (Argumente sortiert)
Fußnoten
- Der Lernende sollte den BubbleSort zunächst kennenlernen, um selbst erfahren zu können, dass der BubbleSort aufgrund seiner schlechten Laufzeit-Komplexität kein brauchbarer Sortieralgorithmus ist.
- Eine derartige Schleifenkorrelation steigert nur die Effizienz des BubbleSorts, jedoch nicht die Laufzeit-Komplexität. Man kann noch so viele Programmiertricks (siehe ShakerSort) einbauen, die quadratische Laufzeit-Komplexität O(n*n) bleibt jedoch erhalten.
Quellenangabe
-
[INFODUDEN]
-
[INFO2002]