next up previous contents
Nächste Seite: 2.3 BubbleSort: Sortieren durch Aufwärts: 2. Sortieren Vorherige Seite: 2.1 Hilfsklassen   Inhalt

Unterabschnitte


2.2 SelectionSort: Sortieren durch Auswählen

Einer der einfachsten Sortieralgorithmen wird ,,Sortieren durch Auswählen`` - im Englischen SelectionSort - genannt.

2.2.1 Algorithmus

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;
    }
  }
  */
}

2.2.2 Visualisierendes Hamster-Programm

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();
}

2.2.3 Analyse des Algorithmus

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 $\approx$ $n^2/2$. Das gilt in allen Fällen,

Die Anzahl an Vertauschungen von Array-Elementen beträgt

Insbesondere bedeutet dass, das jedes Array-Element maximal einmal bewegt wird.

Im Web finden sich zahlreiche weitere Informationen zum SelectionSort-Algorithmus, z.B. unter


next up previous contents
Nächste Seite: 2.3 BubbleSort: Sortieren durch Aufwärts: 2. Sortieren Vorherige Seite: 2.1 Hilfsklassen   Inhalt
Dietrich Boles 2005-04-18