Selection-sort

Einführung

Ein einfacher Sortieralgorithmus ist der Selection Sort. 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 erster Stelle befindet. Anschließend wird das zweitkleinste Element gesucht und mit dem Element an zweiter Stelle vertauscht usw. 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 4) wird mit dem Wert an der Position des kleinsten Elements (hier 1 an 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, daher ist dort keine Suche mehr erforderlich. Der restliche Teil der Liste wird durchsucht. Das kleinste Element befindet sich hier am Ende der Liste. 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 Schritt für Schritt. 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 SelectionSort.

Um eine Datenstruktur (z. B. ein Array) mit n Einträgen mittels SelectionSort zu sortieren, muss n−1-mal das Minimum durch Vergleichen bestimmt werden. Bei der ersten Bestimmung des Minimums sind n−1 Vergleiche notwendig, bei der zweiten n−2 Vergleiche usw. Mit der gaußschen Summenformel erhält man die Gesamtanzahl der notwendigen Vergleiche:

(n − 1) + (n − 2) + … + 1 = n(n − 1) / 2

SelectionSort liegt somit in der Komplexitätsklasse [math]\displaystyle{ O(n^2) }[/math].