In den folgenden Abschnitten werden die einzelnen Sortieralgorithmen vorgestellt und es werden objektorientierte Hamster-Programme entwickelt, die die Funktionsweise der Algorithmen demonstrieren. Die Programme bzw. Klassen greifen dabei auf einige Hilfsklassen zurück, die in diesem Abschnitt vorgestellt werden.
Die erweiterte Hamster-Klasse AllroundHamster (AllroundHamster.ham) erweitert den Befehlsvorrat der Hamster um einige nützliche Befehle.
// die Klasse erweitert den Befehlssatz eines normalen
// Hamsters um viele nuetzliche Befehle
public class AllroundHamster extends Hamster {
protected boolean mitErlaeuterungen;
// gibt an, ob textuelle Erlaeuterungen ausgegeben werden sollen
// initialisiert einen neuen AllroundHamster mit den
// uebergebenen Werten
public AllroundHamster(int r, int s, int b, int k,
boolean mitErlaeuterungen) {
super(r, s, b, k);
this.mitErlaeuterungen = mitErlaeuterungen;
}
// initialisiert einen neuen AllroundHamster mit den
// uebergebenen Werten
public AllroundHamster(int r, int s, int b, int k) {
this(r, s, b, k, false);
}
// initialisiert einen neuen AllroundHamster mit den
// Attributwerten eines bereits existierenden Hamsters
public AllroundHamster(Hamster existierenderHamster,
boolean mitErlaeuterungen) {
this(existierenderHamster.getReihe(),
existierenderHamster.getSpalte(),
existierenderHamster.getBlickrichtung(),
existierenderHamster.getAnzahlKoerner(),
mitErlaeuterungen
);
}
// initialisiert einen neuen AllroundHamster mit den
// Attributwerten eines bereits existierenden Hamsters
public AllroundHamster(Hamster existierenderHamster) {
this(existierenderHamster, false);
}
// gibt eine Erlaeuterung auf den Bildschirm aus
public void erlaeuterung(String text) {
if (this.mitErlaeuterungen) {
this.schreib(text);
}
}
// der Hamster dreht sich um 180 Grad
public void kehrt() {
this.linksUm();
this.linksUm();
}
// der Hamster dreht sich nach rechts
public void rechtsUm() {
this.kehrt();
this.linksUm();
}
// der Hamster laeuft "anzahl" Schritte, maximal jedoch
// bis zur naechsten Mauer;
// geliefert wird die tatsaechliche Anzahl gelaufener
// Schritte
public int vor(int anzahl) {
int schritte = 0;
while (this.vornFrei() && anzahl > 0) {
this.vor();
schritte = schritte + 1;
anzahl = anzahl - 1;
}
return schritte;
}
// der Hamster legt "anzahl" Koerner ab, maximal jedoch
// so viele, wie er im Maul hat;
// geliefert wird die tatsaechliche Anzahl abgelegter
// Koerner
public int gib(int anzahl) {
int abgelegteKoerner = 0;
while (!this.maulLeer() && anzahl > 0) {
this.gib();
abgelegteKoerner = abgelegteKoerner + 1;
anzahl = anzahl - 1;
}
return abgelegteKoerner;
}
// der Hamster frisst "anzahl" Koerner, maximal jedoch
// so viele, wie auf der aktuellen Kachel liegen
public int nimm(int anzahl) {
int gefresseneKoerner = 0;
while (this.kornDa() && anzahl > 0) {
this.nimm();
gefresseneKoerner = gefresseneKoerner + 1;
anzahl = anzahl - 1;
}
return gefresseneKoerner;
}
// der Hamster legt alle Koerner, die er im Maul hat,
// auf der aktuellen Kachel ab;
// geliefert wird die Anzahl abgelegter Koerner
public int gibAlle() {
int abgelegteKoerner = 0;
while (!this.maulLeer()) {
this.gib();
abgelegteKoerner = abgelegteKoerner + 1;
}
return abgelegteKoerner;
}
// der Hamster frisst alle Koerner auf der aktuellen Kachel;
// geliefert wird die Anzahl gefressener Koerner
public int nimmAlle() {
int gefresseneKoerner = 0;
while (this.kornDa()) {
this.nimm();
gefresseneKoerner = gefresseneKoerner + 1;
}
return gefresseneKoerner;
}
// der Hamster laeuft bis zur naechsten Mauer;
// geliefert wird die Anzahl ausgefuehrter Schritte
public int laufeZurWand() {
int schritte = 0;
while (this.vornFrei()) {
this.vor();
schritte = schritte + 1;
}
return schritte;
}
// der Hamster testet, ob links von ihm die Kachel frei ist
public boolean linksFrei() {
this.linksUm();
boolean frei = this.vornFrei();
this.rechtsUm();
return frei;
}
// der Hamster testet, ob rechts von ihm die Kachel frei ist
public boolean rechtsFrei() {
this.rechtsUm();
boolean frei = this.vornFrei();
this.linksUm();
return frei;
}
// der Hamster testet, ob hinter ihm die Kachel frei ist
public boolean hintenFrei() {
this.kehrt();
boolean frei = this.vornFrei();
this.kehrt();
return frei;
}
// der Hamster dreht sich so lange um, bis er in die
// uebergebene Blickrichtung schaut
public void setzeBlickrichtung(int richtung) {
while (this.getBlickrichtung() != richtung) {
this.linksUm();
}
}
// der Hamster laeuft in der Spalte, in der er
// gerade steht, zur angegebenen Reihe;
// Voraussetzung: die Reihe existiert und
// es befinden sich keine Mauern
// im Territorium bzw. auf dem gewaehlten Weg
public void laufeZuReihe(int reihe) {
if (reihe == this.getReihe()) return;
if (reihe > this.getReihe()) {
this.setzeBlickrichtung(Hamster.SUED);
} else {
this.setzeBlickrichtung(Hamster.NORD);
}
while (reihe != this.getReihe()) {
this.vor();
}
}
// der Hamster laeuft in der Reihe, in der er
// gerade steht, zur angegebenen Spalte;
// Voraussetzung: die Spalte existiert und
// es befinden sich keine Mauern
// im Territorium bzw. auf dem gewaehlten Weg
public void laufeZuSpalte(int spalte) {
if (spalte == this.getSpalte()) return;
if (spalte > this.getSpalte()) {
this.setzeBlickrichtung(Hamster.OST);
} else {
this.setzeBlickrichtung(Hamster.WEST);
}
while (spalte != this.getSpalte()) {
this.vor();
}
}
// der Hamster laeuft zur Kachel (reihe/spalte);
// Voraussetzung: die Kachel existiert und
// es befinden sich keine Mauern
// im Territorium bzw. auf dem gewaehlten Weg
public void laufeZuKachel(int reihe, int spalte) {
laufeZuReihe(reihe);
laufeZuSpalte(spalte);
}
}
Hamster, die die eigentliche Sortierung der Körnerhaufen durchführen, werden von von der Klasse KoernerHaufenSortierHamster (KoernerHaufenSortierHamster.ham) abgeleiteten Klassen erzeugt, die wiederum von der Klasse AllroundHamster abgeleitet ist und nützliche Methoden zum Sortieren bereitstellt.
// Basisklasse der eigentlichen Hamster-Sortier-Klassen
public class KoernerHaufenSortierHamster extends AllroundHamster {
protected int startSpalte = 0;
// Spalte, in der der Sortier-Hamster anfangs steht
// Konstruktor
protected KoernerHaufenSortierHamster(boolean erlaeuterungen) {
super(Hamster.getStandardHamster(), erlaeuterungen);
this.startSpalte = this.getSpalte();
}
// ermittelt und liefert die Anzahl der zu sortierenden
// Koernerhaufen
protected int ermittleAnzahlKoernerHaufen() {
// bis zur naechsten Mauer
int anzahlKoernerHaufen = 0;
while (this.vornFrei()) {
this.vor();
anzahlKoernerHaufen++;
}
// und zurueck (Seiteneffekte beseitigen)
this.kehrt();
int speicher = anzahlKoernerHaufen;
while (speicher > 0) {
this.vor();
speicher = speicher - 1;
}
this.kehrt();
return anzahlKoernerHaufen;
}
// laeuft zum angegebenen Koernerhaufenindex
protected void laufeZuIndex(int index) {
this.laufeZuSpalte(this.startSpalte + index + 1);
}
// liefert den aktuellen Index des Koernerhaufens, auf dem der Hamster steht
protected int liefereIndex() {
return this.getSpalte() - this.startSpalte - 1;
}
// liefert die Anzahl an Koernern des Koernerhaufens, auf dem der Hamster steht
protected int liefereAnzahlKoerner() {
return Territorium.getAnzahlKoerner(this.getReihe(), this.getSpalte());
}
}
Um die Funktionsweise der jeweiligen Sortieralgorithmen zu demonstrieren, werden Hamster eingesetzt, die bestimmte Körnerhaufen markieren. Diese Hamster werden von der Klasse MarkierungsHamster (MarkierungsHamster.ham) erzeugt.
// zum Markieren bestimmter Koernerhaufen
public class MarkierungsHamster extends AllroundHamster {
private int startSpalte;
// Spalte, in der der Hamster erzeugt wird
private int koernerHaufenReihe;
// Reihe, in der die Koernerhaufen liegen
// Konstruktor
public MarkierungsHamster(int reihe, int spalte, int koernerHaufenReihe,
boolean mitErlaeuterungen) {
super(reihe, spalte, Hamster.NORD, 0, mitErlaeuterungen);
this.startSpalte = spalte;
this.koernerHaufenReihe = koernerHaufenReihe;
}
// laeuft zum angegebenen Koernerhaufenindex
public void markiereIndex(int index) {
this.laufeZuSpalte(this.startSpalte + index + 1);
this.setzeBlickrichtung(Hamster.NORD);
}
// liefert den markierten Koernerhaufenindex
public int liefereIndex() {
return this.getSpalte() - this.startSpalte - 1;
}
// liefert die Anzahl an Koernern des markierten Koernerhaufens
public int liefereAnzahlKoerner() {
return
Territorium.getAnzahlKoerner(this.koernerHaufenReihe, this.getSpalte());
}
// kehrt zur Startspalte zurueck
public void laufeZuStartSpalte() {
this.laufeZuSpalte(this.startSpalte);
this.setzeBlickrichtung(Hamster.NORD);
}
}
Hamster der Klasse BooleanHamster (BooleanHamster.ham) repräsentieren die beiden Wahrheitswerte. Schaut ein Boolean-Hamster nach Nordern kennzeichnet er den Wert true, schaut er nach Osten, kennzeichnet er den Wert false.
// demonstriert die Wahrheitswerte wahr und falsch
public class BooleanHamster extends AllroundHamster {
// Konstruktor
public BooleanHamster(int reihe, int spalte, boolean wahr,
boolean mitErlaeuterungen) {
super(reihe, spalte, Hamster.NORD, 0, mitErlaeuterungen);
this.deuteAn(wahr);
}
// deutet den angegebenen Wert an
public void deuteAn(boolean wahr) {
if (wahr) {
this.setzeBlickrichtung(Hamster.NORD);
} else {
this.setzeBlickrichtung(Hamster.OST);
}
}
// liefert den angedeuteten Wert
public boolean istWahr() {
return this.getBlickrichtung() == Hamster.NORD;
}
}