Eine Variante des SelectionSort-Algorithmus, die man sehr häufig in Lehrbüchern findet, ist der BubbleSort-Algorithmus.
Der BubbleSort-Algorithmus lässt sich folgendermaßen skizzieren:
Gegeben sei ein Array mit n Elementen, das in aufsteigender Reihenfolge sortiert werden soll:
Durch die fortlaufenden Vertauschungen wird im ersten Durchlauf das kleinste Element des Array ganz nach links transportiert, im zweiten Durchlauf wird das zweitkleinste an seine korrekte Position gebracht, usw. Das heisst, das Prinzip von BubbleSort ist identisch mit dem Prinzip von SelectionSort, nur die Suche nach dem jeweils kleinsten Element erfolgt auf eine andere Art und Weise.
Die folgende Klasse BubbleSort (BubbleSort.ham) implementiert das Interface SortierAlgorithmus entsprechend des BubbleSort-Algorithmus:
public class BubbleSort implements SortierAlgorithmus {
// sortiert das uebergebene Array in aufsteigender Reihenfolge
// gemaess dem BubbleSort-Algorithmus
public void sortiere(int[] zahlen) {
boolean tauschStattgefunden = true;
int anzahlSortierteZahlen = 0;
do {
tauschStattgefunden = false;
for (int aktIndex = zahlen.length-1;
aktIndex > anzahlSortierteZahlen;
aktIndex--) {
if (zahlen[aktIndex] < zahlen[aktIndex-1]) {
tauscheElemente(zahlen, aktIndex, aktIndex-1);
tauschStattgefunden = true;
}
}
anzahlSortierteZahlen++;
} while (tauschStattgefunden);
}
// vertauscht im Array die Elemente der angegebenen Indizes
private void tauscheElemente(int[] zahlen, int index1, int index2) {
int speicher = zahlen[index1];
zahlen[index1] = zahlen[index2];
zahlen[index2] = speicher;
}
/* der BubbleSort-Algorithmus in kompakter Form
public void sortiere(int[] zahlen) {
boolean tauschStattgefunden = true;
int anzahlSortierteZahlen = 0;
do {
tauschStattgefunden = false;
for (int aktIndex = zahlen.length-1;
aktIndex > anzahlSortierteZahlen;
aktIndex--) {
if (zahlen[aktIndex] < zahlen[aktIndex-1]) {
int speicher = zahlen[aktIndex];
zahlen[aktIndex] = zahlen[aktIndex-1];
zahlen[aktIndex-1] = speicher;
tauschStattgefunden = true;
}
}
anzahlSortierteZahlen++;
} while (tauschStattgefunden);
}
*/
}
Die folgende Hamster-Klasse BubbleSortHamster (BubbleSortHamster.ham) implementiert das Interface SortierHamster und visualisiert dabei den BubbleSort-Algorithmus. Voraussetzung ist, dass es im Territorium zwei nicht durch Mauern blockierte Reihen unterhalb des Standard-Hamsters gibt. Ein Körnerhaufensortierhamster als Vertretungshamster des Standard-Hamsters (roter Hamster) durchläuft - so lange Vertauschungen stattgefunden haben - von rechts nach links den unsortierten Teil der Körnerhaufen und führt dabei notwendige Vertauschungen durch. In der ersten Reihe unterhalb der Körnerhaufenreihe markiert ein Markierungshamster (grüner Hamster) den rechten Index des sortierten Teils. Ein Boolean-Hamster (gelber Hamster) in der zweiten Reihe deutet an, ob im aktuellen Durchlauf Vertauschungen stattgefunden haben (Blickrichtung ist Nord) oder nicht (Blickrichtung ist Ost).
// Demonstartion des BubbleSort-Algorithmus
public class BubbleSortHamster
extends KoernerHaufenSortierHamster
implements SortierHamster {
private MarkierungsHamster sortiertIndexHamster = null;
// markiert das Ende des sortierten Teils
private BooleanHamster tauschStattgefundenHamster = null;
// zeigt an, ob in einem Durchlauf ein Tausch stattgefunden hat
private int anzahlKoernerHaufen = 0;
// Anzahl der zu sortierenden Koernerhaufen
// Konstruktor
public BubbleSortHamster(boolean mitErlaeuterungen) {
super(mitErlaeuterungen);
this.erlaeuterung(
"Ich sortiere die Koernerhaufen auf der Basis des BubbleSort-Algorithmus.");
this.sortiertIndexHamster =
new MarkierungsHamster(this.getReihe() + 1, this.getSpalte(),
this.getReihe(), mitErlaeuterungen);
this.sortiertIndexHamster.erlaeuterung(
"Ich markiere das Ende des sortierten Teils.");
this.tauschStattgefundenHamster =
new BooleanHamster(this.getReihe() + 2, this.getSpalte(),
false, mitErlaeuterungen);
this.tauschStattgefundenHamster.erlaeuterung(
"Ich deute an, ob in einem Durchlauf ein Tausch stattgefunden hat.");
}
// Der Standard-Hamster steht mit Blickrichtung OST irgendwo im Territorium.
// Ein Vertretungshamster soll die Koernerhaufen bis zur nächsten Wand in
// aufsteigender Reihenfolge sortieren.
// Voraussetzung: Unterhalb des Standard-Hamsters existieren zwei nicht
// durch Mauern blockierte Reihen.
public void sortiereKoernerHaufen() {
this.erlaeuterung(
"Ich zaehle nun die Anzahl der zu sortierenden Koernerhaufen.");
this.anzahlKoernerHaufen = this.ermittleAnzahlKoernerHaufen();
this.erlaeuterung(
"Die Anzahl der zu sortierenden Koernerhaufen betraegt " +
this.anzahlKoernerHaufen +
",\nd.h. die Indizes der Haufen liegen zwischen 0 und " +
(this.anzahlKoernerHaufen-1) +
".");
do {
this.tauschStattgefundenHamster.deuteAn(false);
// laufe nach vorne bis zum Anfang des unsortierten Teils
this.erlaeuterung(
"Ich transportiere nun den kleinsten Koernerhaufen im unsortierten Teil," +
"\nd.h. zwischen den Indizes " +
(this.sortiertIndexHamster.liefereIndex()+1) + " und " +
(anzahlKoernerHaufen-1) + ", zum Index " +
(this.sortiertIndexHamster.liefereIndex()+1) +
".");
for (int aktIndex = anzahlKoernerHaufen-1;
aktIndex > this.sortiertIndexHamster.liefereIndex()+1;
aktIndex--) {
this.laufeZuIndex(aktIndex);
this.setzeBlickrichtung(Hamster.WEST);
// vergleiche benachbarte Koernerhaufen und tausche,
// falls der hintere Haufen kleiner ist
if (anzahlKoernerAktIndex() < anzahlKoernerAktIndexMinus1()) {
this.erlaeuterung(
"Der Koernerhaufen beim Index " +
aktIndex +
" ist kleiner als der Koernerhaufen beim Index " +
(aktIndex-1) +
".\nDaher tausche ich sie.");
koernerHaufenTauschen();
this.tauschStattgefundenHamster.deuteAn(true);
}
}
this.sortiertIndexHamster.markiereIndex(
this.sortiertIndexHamster.liefereIndex()+1);
} while (this.tauschStattgefundenHamster.istWahr());
this.erlaeuterung(
"Im letzten Durchlauf hat kein Tausch mehr stattgefunden," +
"\nd.h. die Koernerhaufen sind sortiert.");
beendeSortierung();
}
private void koernerHaufenTauschen() {
int koernerAnzahl1 = this.nimmAlle();
this.vor();
int koernerAnzahl2 = this.nimmAlle();
this.gib(koernerAnzahl1);
this.kehrt();
this.vor();
this.gib(koernerAnzahl2);
}
private void beendeSortierung() {
this.laufeZuSpalte(this.startSpalte);
this.setzeBlickrichtung(Hamster.OST);
this.erlaeuterung("Sortierung erfolgreich beendet!");
}
private int anzahlKoernerAktIndex() {
return Territorium.getAnzahlKoerner(this.getReihe(), this.getSpalte());
}
private int anzahlKoernerAktIndexMinus1() {
return Territorium.getAnzahlKoerner(this.getReihe(), this.getSpalte()-1);
}
}
Mit dem folgendem objektorientierten Hamster-Programm (SortierenMitBubbleSort) (SortierenMitBubbleSort.ham) können Sie sich von den Hamstern den BubbleSort-Algorithmus demonstrieren lassen.
void main() {
Hamster paul = Hamster.getStandardHamster();
String antwort =
Hamster.getStandardHamster().liesZeichenkette(
"Moechten Sie textuelle Erlaeuterungen (ja/nein)?");
SortierHamster sortierer = new BubbleSortHamster(antwort.equals("ja"));
sortierer.sortiereKoernerHaufen();
}
Der BubbleSort-Algorithmus ist stabil und arbeitet in-place.
Sei n die Anzahl an zu sortierenden Elementen. Die Anzahl an Vergleichen zwischen den Array-Elementen beträgt
, wenn das Array bereits aufsteigend sortiert ist,
, wenn das Array absteigend sortiert ist,
, wenn die Anordnung der Elemente im Array zufällig ist.
Die Anzahl an Vertauschungen von Array-Elementen beträgt
, wenn das Array bereits aufsteigend sortiert ist,
, wenn das Array absteigend sortiert ist,
, wenn die Anordnung der Elemente im Array zufällig ist.
Im Web finden sich zahlreiche weitere Informationen zum BubbleSort-Algorithmus, z.B. unter