Selectionsort

Selection Sort Erklärung

Was genau ist nun eigentlich Selection Sort? Beim Selection Sort handelt es sich um einen Algorithmus, der Datenmengen durch Auswahl sortiert. Vom Prinzip her wird dabei immer entweder nach dem kleinsten oder dem größten Element gesucht.

Selection Sort Definition

Selection Sort Algorithmus

Wie genau arbeitet jetzt der Algorithmus, der hinter dem Selection Sort steckt? Am besten lässt sich das an einem Beispiel zeigen. Gegeben ist ein Array [5, 2, 8, 4, 9, 7], das sortiert werden soll.

Und das war es schon – fertig ist Dein mit Selection Sort sortiertes Array. Wie Du siehst, geht der Algorithmus im Grunde einfach durch die Datenmenge und schaut – in diesem Fall – immer nach dem kleinsten Element, das er dann mit dem ersten Element in der unsortierten Reihe vertauscht.

Selection Sort Vorgehensweise

Noch mal kurz und knapp zusammengefasst, wie der Algorithmus abläuft, wenn aufsteigend beginnend beim kleinsten Element sortiert werden soll:

1. Minimalwert auf Position 0 festlegen.
2. Array durchgehen, um das kleinste Element zu finden.
3. Wird ein Element gefunden, das kleiner als der zuvor festgelegte Minimalwert ist, dann vertausche beide Werte miteinander.
4. Gehe dann einen Schritt nach rechts.
5. Wiederhole das Ganze, bis das Array fertig sortiert ist.

Selection Sort Komplexität

Für Dich auch noch interessant zu wissen, wie es eigentlich mit der Komplexität vom Selection Sort aussieht?

Beim Selection Sort handelt es sich um einen einfachen Sortieralgorithmus mit einer quadratischen Laufzeit O(n²). Das liegt daran, dass der Algorithmus zwei ineinander verschachtelte Schleifen enthält.

Warum zwei Schleifen? In der ersten Schleife wird ein Element des Arrays einzeln ausgewählt. Die nächste Schleife vergleicht dann dieses Element mit allen anderen Elementen aus dem Array. Beide Vorgänge haben eine Komplexität von O(n), die Gesamtkomplexität beträgt also O(n) • O(n) = O(n²).

Platzkomplexität

Das Sortieren von Elementen läuft beim Selection Sort in-place – also an Ort und Stelle – ab. Außerdem arbeitet der Algorithmus konstant, da egal, wie viele Elemente sortiert werden sollen, immer die gleiche Anzahl an Hilfsvariablen benötigt wird. Das heißt, die Platzkomplexität beträgt in diesem Fall O(1).

Selection Sort – Weitere Begrifflichkeiten

In den nächsten Abschnitten werden noch weitere wichtige Begrifflichkeiten rund um das Sortierverfahren Selection Sort erklärt. Folgende Begriffe werden dabei besprochen:

• stabil vs. instabil
• vergleichsbasiert vs. nicht vergleichsbasiert
• iterativ vs. rekursiv
• Parallelisierbarkeit

Selection Sort stabil – instabil

Auf den ersten Blick erscheint Selection Sort stabil: Tauchen im unsortierten Teil eines Arrays Elemente mit demselben Wert auf, sollte man annehmen, dass das erste davon auch als Erstes im bereits sortierten Abschnitt landet. Das ist jedoch nicht zwingend der Fall, da es sein kann, dass der Algorithmus durch das Vertauschen von Elementen im unsortierten Abschnitt die ursprüngliche Reihenfolge durcheinander bringt.

Haben am Ende zwei Elemente denselben Wert, würde der Algorithmus diese nicht noch einmal miteinander tauschen – denn sie haben ja bereits die richtige Reihenfolge. Der Sortieralgorithmus ist somit instabil!

Selection Sort stabil

Wie kann Selection Sort nun stabil gemacht werden? Das kannst Du erreichen, indem Du die Elemente nicht vertauscht, sondern alles zwischen dem ersten und dem kleinsten Element um eine Position nach rechts verschiebst und das kleinste Element auf die vordere Position setzt.

Positiv ist, dass die Laufzeit dadurch grundsätzlich nicht beeinträchtigt wird. Wird allerdings ein Array durchsucht, sorgen die zusätzlichen Verschiebungen für eine deutlich schlechtere Performance. Bei verketteten Listen könnte diese Methode jedoch ohne große Performance-Einbußen durchgeführt werden.

Selection Sort vergleichsbasiert

Selection Sort ist ein vergleichsbasierter Sortieralgorithmus. Das heißt, der Algorithmus vergleicht immer zwei Elemente eines Datensatzes miteinander auf ein bestimmtes Kriterium.

Selection Sort iterativ – rekursiv

Selection Sort wird in der Regel iterativ implementiert, Du kannst ihn jedoch auch rekursiv verwenden. Was Du dabei bedenken solltest: Die Komplexität bleibt die gleiche wie bei der iterativen Variante – also O(n²). Die Platzkomplexität beträgt bei der rekursiven Variante allerdings O(n) statt O(1).

Selection Sort Parallelisierbarkeit

Selection Sort ist theoretisch zu Teilen parallelisierbar, das heißt: Die äußere Schleife lässt sich nicht parallelisieren, die innere schon. Bei der inneren Schleife könntest Du das Array aufteilen und in jedem Teilarray jeweils parallel nach dem kleinsten Element suchen und am Ende führst Du die Ergebnisse zusammen. Bei der äußeren Schleife geht das nicht, da diese den Inhalt des Arrays mit jedem Schritt verändert.

Selection Sort Zusammenfassung

Was solltest Du bisher gelernt haben? In der nachfolgenden Übersicht findest Du die wichtigsten Aspekte des Selection Sort noch einmal zusammengefasst.

Selection Sort Vorteile – Nachteile

Da Selection Sort nicht der einzige existierende Sortieralgorithmus ist, sollte klar sein, dass der Algorithmus verschiedene Vor- und Nachteile hat.

Doch warum arbeitet das Sortierverfahren eher ineffizient? Das liegt daran, dass im Gegensatz zu Verfahren wie Quicksort oder Mergesort relativ viele Vergleiche notwendig sind. Das heißt, der Algorithmus arbeitet mit seiner quadratischen Laufzeit sehr kostenintensiv.

Das ist übrigens auch der Grund, warum sich der Selection Sort Algorithmus für kleinere Datenmengen besser eignet als für größere. Da mit wachsenden Daten auch die Laufzeit quadratisch mitwächst.

Selection Sort Beispiel

Damit Du Dir besser vorstellen kannst, wie Selection Sort arbeitet, bekommst Du in den folgenden Abschnitten noch ein paar konkrete Beispiele vorgestellt.

Wie und wo könnte Selection Sort nun angewendet werden? Ein häufiges Beispiel ist dafür das Sortieren von Spielkarten oder generell das Sortieren von unsortierten Zahlenmengen.

Generell eignet sich der Sortieralgorithmus, wenn:

• kleine Datenmengen sortiert werden sollen.
• die Überprüfung aller Elemente verpflichtend ist.
• die "Kosten" für den Austausch keine Rolle spielen.

Selection Sort Pseudocode

Wie könnte jetzt der Pseudocode eines Selection Sorts aussehen? Bei der Eingabe wirst Du eine Liste aus unsortierten Daten haben:

Array A[1 … n] von n Elementen

Als Ausgabe möchtest Du eine sortierte Liste dieser Elemente bekommen. Der Pseudocode dafür könnte z. B. wie folgt aussehen:

for Element Eins = 1 to Arraylaenge - 1 
    do
    min = Element Eins
         for Element Zwei = Element Eins + 1 to Arraylaenge - 1 do
                if Array[Element Zwei] < Array[min] then
                min = Element Zwei
                end if
         end for
    Swap Array[min] and Array[Element Eins]
end for

Beim Pseudocode wird der kleinste Wert zunächst auf 1 gesetzt. Danach wird die äußere Schleife so lange durchgegangen wie Arraylaenge - 1 machbar ist, also bis alle Werte im Array durchgelaufen sind. Innerhalb dieser Schleife sucht eine weitere Schleife jeweils nach einem kleineren Wert als dem aktuellen, wird dieser gefunden, werden die Werte im Anschluss miteinander vertauscht (Swap Array[min] and Array[Element Eins]).

Selection Sort Java

Zum Abschluss folgt noch ein kleines Beispiel von einem Selection Sort in Java Code:

import java.util.Arrays;

class SelectionSort {

void selectionSort(int array[]) {

    int size = array.length;

// Grenze des unsortierten Arrays einzeln verschieben

    for (int point = 0; point < size - 1; point ++) {
        int min_idx = point;
        for (int i = point + 1; i < size; i++) {

            // wählt das kleinste Element in jeder Schleife aus

            if (array[i] < array[min_idx]) {
            min_idx = i;
            }
        }

        // setzt den kleinsten Wert an die richtige Position 

        int temp = array[point];
        array[point] = array[min_idx];
        array[min_idx] = temp;
        }
    }

// Code für die Systemausgabe

public static void main(String args[]) {
    int[] data = { 5, 2, 8, 4, 9, 7 };
    SelectionSort ss = new SelectionSort();
    ss.selectionSort(data);
    System.out.println("Sortiertes Array in aufsteigender Reihenfolge: ");
    System.out.println(Arrays.toString(data));
    }
}

Als Ausgabe erhältst Du die fertig sortierte Liste.

Sortiertes Array in aufsteigender Reihenfolge: 2 4 5 7 8 9