Einer der einfachsten Sortieralgorithmen wird ,,Sortieren durch Auswählen`` - im Englischen SelectionSort - genannt.
Der SelectionSort-Algorithmus lässt sich folgendermaßen skizzieren:
Gegeben sei ein Array mit n Elementen, das in aufsteigender Reihenfolge sortiert werden soll:
Das Array besteht also aus einem sortierten vorderen Teil, der in jedem Schritt um ein Element wächst, und einem unsortierten hinteren Teil, der entsprechend schrumpft. D.h. bei der Suche nach dem x-kleinsten Element muss nur noch der unsortierte hintere Teil des Arrays ab dem x-ten Element durchsucht werden, da die ersten x-1 Elemente bereits sortiert sind. Genauer gesagt, muss in jedem Schritt jeweils das kleinste Element des unsortierten Teils gesucht und mit dem ersten Element des unsortierten Teils vertauscht werden.
Die folgende Klasse SelectionSort (SelectionSort.ham) implementiert das Interface SortierAlgorithmus entsprechend des SelectionSort-Algorithmus:
public class SelectionSort implements SortierAlgorithmus { // sortiert das übergebene Array in aufsteigender Reihenfolge // gemaess dem SelectionSort-Algorithmus public void sortiere(int[] zahlen) { for (int aktIndex = 0; aktIndex < zahlen.length - 1; aktIndex++) { int minIndex = sucheKleinstesElement(zahlen, aktIndex); tauscheElemente(zahlen, aktIndex, minIndex); } } // sucht im Array ab dem angegebenen Index das kleinste Element // und liefert dessen Index private int sucheKleinstesElement(int[] zahlen, int abIndex) { int minIndex = abIndex; for (int suchIndex = abIndex+1; suchIndex < zahlen.length; suchIndex++) { if (zahlen[suchIndex] < zahlen[minIndex]) { // neues kleinstes Element gefunden minIndex = suchIndex; } } return minIndex; } // 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 SelectionSort-Algorithmus in kompakter Form public void selection(int[] zahlen) { for (int aktIndex = 0; aktIndex < zahlen.length - 1; aktIndex++) { int minIndex = aktIndex; for (int suchIndex = aktIndex+1; suchIndex < zahlen.length; suchIndex++) { if (zahlen[suchIndex] < zahlen[minIndex]) { minIndex = suchIndex; } } int speicher = zahlen[aktIndex]; zahlen[aktIndex] = zahlen[minIndex]; zahlen[minIndex] = speicher; } } */ }
Die folgende Hamster-Klasse SelectionSortHamster (SelectionSortHamster.ham) implementiert das Interface SortierHamster und visualisiert dabei den SelectionSort-Algorithmus. Voraussetzung ist, dass es im Territorium zwei nicht durch Mauern blockierte Reihen unterhalb des Standard-Hamsters gibt. Während ein Körnerhaufensortierhamster als Vertretungshamster des Standard-Hamsters (roter Hamster) jeweils den unsortierten Teil der Körnerhaufen nach dem kleinsten Element durchsucht, markiert in der ersten Reihe unterhalb der Körnerhaufenreihe ein Markierungshamster (grüner Hamster) den aktuellen Index, d.h. er zeigt auf das erste Element des unsortierten Teils. Ein weiterer Markierungshamster (gelber Hamster), eine weitere Reihe darunter, markiert das aktuell kleinste Element während der Suche nach dem kleinsten Element.
// Demonstration des SelectionSort-Algorithmus public class SelectionSortHamster extends KoernerHaufenSortierHamster implements SortierHamster { private MarkierungsHamster aktIndexHamster = null; // markiert den Start des unsortierten Teils private MarkierungsHamster minIndexHamster = null; // markiert den jeweils kleinsten Koernerhaufen im unsortierten Teil private int anzahlKoernerHaufen = 0; // Anzahl der zu sortierenden Koernerhaufen // Konstruktor public SelectionSortHamster(boolean mitErlaeuterungen) { super(mitErlaeuterungen); this.erlaeuterung( "Ich sortiere die Koernerhaufen auf der Basis des " + "SelectionSort-Algorithmus."); this.aktIndexHamster = new MarkierungsHamster(this.getReihe()+1, this.getSpalte(), this.getReihe(), mitErlaeuterungen); this.aktIndexHamster.erlaeuterung( "Ich markiere den linken Koernerhaufen des unsortierten Teils."); this.minIndexHamster = new MarkierungsHamster(this.getReihe()+2, this.getSpalte(), this.getReihe(), mitErlaeuterungen); this.minIndexHamster.erlaeuterung( "Ich markiere den aktuell kleinsten Koernerhaufen im unsortierten Teil."); } // 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) + "."); // durchlaufe die Menge der Koernerhaufen von links nach rechts; // merke dir den aktuellen Koernerhaufen for (int aktIndex=0; aktIndex<this.anzahlKoernerHaufen-1; aktIndex++) { // suche den kleinsten Koernerhaufen im unsortierten Teil this.sucheMinKoernerHaufen(aktIndex); // tausche den aktuellen Koernerhaufen mit dem kleinsten // Koernerhaufen im unsortierten Teil this.aktUndMinKoernerHaufenTauschen(); this.erlaeuterung( "Die Koernerhaufen zwischen den Indizes 0 und " + aktIndex + " sind nun sortiert."); } beendeSortierung(); } private void sucheMinKoernerHaufen(int aktIndex) { // zunaechst ist der aktuelle Koernerhaufen auch der kleinste // im unsortierten Teil this.aktIndexHamster.markiereIndex(aktIndex); this.minIndexHamster.markiereIndex(aktIndex); this.erlaeuterung( "Ich suche nun den kleinsten Koernerhaufen im unsortierten Teil,\n" + "d.h. zwischen den Indizes " + aktIndex + " und " + (this.anzahlKoernerHaufen-1) + "."); // suche im unsortierten Teil der Koernerhaufen den kleinsten for (int suchIndex=aktIndex+1; suchIndex<this.anzahlKoernerHaufen; suchIndex++) { this.laufeZuIndex(suchIndex); if (this.liefereAnzahlKoerner() < this.minIndexHamster.liefereAnzahlKoerner()) { // neuer kleinster Koernerhaufen gefunden this.minIndexHamster.markiereIndex(suchIndex); } } this.erlaeuterung( "Der kleinste Koernerhaufen zwischen den Indizes " + aktIndex + " und " + (this.anzahlKoernerHaufen-1) + " befindet sich bei Index " + this.minIndexHamster.liefereIndex() + "."); } private void aktUndMinKoernerHaufenTauschen() { if (this.aktIndexHamster.liefereIndex() != this.minIndexHamster.liefereIndex()) { this.erlaeuterung( "Ich tausche nun die markierten Koernerhaufen der Indizes " + this.aktIndexHamster.liefereIndex() + " und " + this.minIndexHamster.liefereIndex() + "."); this.laufeZuIndex(this.minIndexHamster.liefereIndex()); int minKoerner = this.nimmAlle(); this.laufeZuIndex(this.aktIndexHamster.liefereIndex()); int aktKoerner = this.nimmAlle(); this.gib(minKoerner); this.laufeZuIndex(this.minIndexHamster.liefereIndex()); this.gib(aktKoerner); } else { this.erlaeuterung( "Der Koernerhaufen links im unsortierten Teil ist auch der kleinste.\n" + "Daher brauche ich nicht zu tauschen."); } } private void beendeSortierung() { this.laufeZuSpalte(this.startSpalte); this.setzeBlickrichtung(Hamster.OST); this.erlaeuterung("Sortierung erfolgreich beendet!"); } }
Mit dem folgendem objektorientierten Hamster-Programm (SortierenMitSelectionSort) (SortierenMitSelectionSort.ham) können Sie sich von den Hamstern den SelectionSort-Algorithmus demonstrieren lassen.
void main() { Hamster paul = Hamster.getStandardHamster(); String antwort = Hamster.getStandardHamster().liesZeichenkette( "Moechten Sie textuelle Erlaeuterungen (ja/nein)?"); SortierHamster sortierer = new SelectionSortHamster(antwort.equals("ja")); sortierer.sortiereKoernerHaufen(); }
Die vorgestellte Implementierung des SelectionSort-Algorithmus ist stabil2.2. SelectionSort arbeitet in-place.
Sei n die Anzahl an zu sortierenden Elementen. Die Anzahl an Vergleichen zwischen den Array-Elementen beträgt . Das gilt in allen Fällen,
Die Anzahl an Vertauschungen von Array-Elementen beträgt
Im Web finden sich zahlreiche weitere Informationen zum SelectionSort-Algorithmus, z.B. unter