Selectionsort

Einführung

Ein einfacher Sortieralgorithmus ist der Selection Sort (Sortieren durch Auswählen). Dieser Algorithmus sucht zunächst das kleinste Element in der Liste, merkt es sich und tauscht es mit dem Element am Anfang aus, sodass sich das kleinste Element an der ersten Stelle befindet.

Anschließend wird das zweitkleinste Element im verbleibenden, noch unsortierten Teil der Liste gesucht und mit dem Element an der zweiten Stelle vertauscht, und so weiter. Auf diese Weise erhalten die Elemente auf der linken Seite der aktuellen Position schrittweise ihren festen Platz und werden nicht mehr verändert.

Beispiel

Es soll eine Liste mit dem Inhalt [4, 3, 1, 5, 2] sortiert werden.

Im ersten Durchlauf wird die komplette Liste durchsucht, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel ist das der Wert 1. Der ursprüngliche Wert der Startposition (hier die 4) wird mit dem Wert an der Position des kleinsten Elements (hier die 1 am Index 2) vertauscht.

Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun bei Index 1. An Index 0 befindet sich bereits das kleinste Element der gesamten Liste, daher ist dort keine Suche mehr erforderlich. Der restliche Teil der Liste wird durchsucht. Es wird die 2 als kleinstes Element ausgewählt und mit der neuen Startposition vertauscht.

Die Suche wiederholt sich nach diesem Prinzip, bis alle Elemente sortiert sind. Der Suchbereich verkleinert sich dabei Schritt für Schritt um ein Element. Die folgende Animation visualisiert den Algorithmus.

Pseudocode

Der Algorithmus sieht im Pseudocode so aus:

prozedur selectionSort(A ist Liste sortierbarer Elemente)
    n = Länge von A
    für einfuegeIndex von 0 bis n - 2 wiederhole
        minPosition = einfuegeIndex
        für idx von einfuegeIndex + 1 bis n - 1 wiederhole
            falls A[idx] < A[minPosition] dann
                minPosition = idx
            ende falls
        ende für
        falls minPosition ≠ einfuegeIndex dann
            vertausche A[minPosition] und A[einfuegeIndex]
        ende falls
    ende für
ende prozedur

Java-Implementierung

public ArrayList<Mitarbeiter> sortierenNachNachnamen() {
    ArrayList<Mitarbeiter> sortierteListe = new ArrayList<>(mitarbeiterListe);
    int stelle = 0;

    while (stelle < sortierteListe.size() - 1) {
        int kleinstesElement = stelle;

        for (int index = stelle + 1; index < sortierteListe.size(); index++) {
            if (sortierteListe.get(index).getNachname()
                    .compareTo(sortierteListe.get(kleinstesElement).getNachname()) < 0) {
                kleinstesElement = index;
            }
        }

        if (kleinstesElement != stelle) {
            Mitarbeiter puffer = sortierteListe.get(kleinstesElement);
            sortierteListe.set(kleinstesElement, sortierteListe.get(stelle));
            sortierteListe.set(stelle, puffer);
        }

        stelle++;
    }

    return sortierteListe;
}

Komplexität

Mit Hilfe der Laufzeitanalyse betrachten wir nun die Zeitkomplexität des Algorithmus Selection Sort.

Ein besonderes Merkmal dieses Algorithmus ist, dass seine Laufzeit **unabhängig** von der anfänglichen Sortierung der Elemente ist. Um eine Datenstruktur (z. B. ein Array) mit [math]\displaystyle{ n }[/math] Einträgen zu sortieren, muss [math]\displaystyle{ n - 1 }[/math] Mal das Minimum durch Vergleichen bestimmt werden.

Bei der ersten Bestimmung des Minimums sind [math]\displaystyle{ n - 1 }[/math] Vergleiche notwendig, bei der zweiten [math]\displaystyle{ n - 2 }[/math] Vergleiche, und so weiter bis zum letzten Durchlauf mit exakt 1 Vergleich. Mit der gaußschen Summenformel erhält man die Gesamtanzahl der immer notwendigen Vergleiche:

[math]\displaystyle{ (n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n }[/math]

Best Case

Das Best-Case-Szenario tritt ein, wenn das Array bereits vollständig aufsteigend sortiert ist. Auch wenn alle Elemente bereits am richtigen Platz stehen, "weiß" der Selection Sort dies nicht. Er muss trotzdem in jedem Durchlauf den kompletten unsortierten Rest der Liste überprüfen, um sicherzustellen, dass nicht doch ein noch kleineres Element existiert. Es finden zwar keine Vertauschungen (Swaps) statt, die Anzahl der Vergleiche bleibt jedoch bei [math]\displaystyle{ \frac{n(n - 1)}{2} }[/math]. Da die Vergleiche asymptotisch dominieren, liegt die Zeitkomplexität im Best Case bei [math]\displaystyle{ \mathcal{O}(n^2) }[/math].

Average Case

Im durchschnittlichen Fall (Average Case) liegt eine zufällig durchmischte Liste vor. Genau wie im Best Case muss der Selection Sort die gesamte arithmetische Reihe an Vergleichen durchführen, um das Minimum in jedem Schritt zu finden. Die Anzahl der durchgeführten Vertauschungen liegt im Schnitt zwischen 0 und [math]\displaystyle{ n - 1 }[/math]. Auch hier ändert dies nichts an der dominanten quadratischen Anzahl der Vergleiche. Die Zeitkomplexität im Average Case ist somit ebenfalls [math]\displaystyle{ \mathcal{O}(n^2) }[/math].

Worst Case

Das Worst-Case-Szenario liegt vor, wenn die Liste in umgekehrter (absteigender) Reihenfolge sortiert ist. Der Algorithmus führt wieder exakt [math]\displaystyle{ \frac{n(n - 1)}{2} }[/math] Vergleiche aus. In diesem Fall muss bei fast jedem Durchlauf (maximal [math]\displaystyle{ n - 1 }[/math] Mal) das kleinste Element mit dem aktuellen Start-Element vertauscht werden. Da die maximale Anzahl der Vertauschungen linear ([math]\displaystyle{ \mathcal{O}(n) }[/math]) wächst, die Anzahl der Vergleiche jedoch quadratisch, bestimmt der quadratische Term das Laufzeitverhalten. Die Komplexitätsklasse im Worst Case liegt demnach bei [math]\displaystyle{ \mathcal{O}(n^2) }[/math].