Theoretische Informatik

Selection Sort

Du fragst dich, wie der Selection Sort funktioniert? Genau das erklären wir dir mit Hilfe eines ausführlichen Beispiels. Im Anschluss zeigen wir dir noch wie sich der Sortieralgorithmus als Pseudocode und Struktogramm aufbauen lässt. Noch dazu kannst du hier die wichtigsten Punkte zu seiner Komplexität erfahren. Am Ende unseres Beitrags findest du noch einen beispielhaften Selection Sort Javacode.

Inhaltsübersicht

Grundidee

Das Sortierverfahren gehört in der Informatik zu den einfachen und instabilen Sortieralgorithmen . Er kann dir auch durch die Begriffe Selectsort oder Exchange Sort bekannt sein.

Das Allgemeine Prinzip kannst du dir als „Sortieren durch Auswahl“ merken. Und das geht in genau zwei Richtungen. Entweder sucht man dabei immer das kleinste (MinSort) oder das größte Element (MaxSort). Das Vorgehen dabei bleibt immer gleich.

Selection Sort, Selectionsort
direkt ins Video springen
Selection Sort

Optimized Selection Sort Algorithm

Eventuell stößt du auch mal auf den Begriff „Optimized Selection Sort Algorithm“ – kurz OSSA genannt. Dabei handelt es sich um einen alternativen Ansatz des Selectionsorts. Dabei werden beide Optionen der Sortierung gleichzeitig angewendet, heißt also, dass der MinSort und Maxsort parallel, gemeinsam arbeiten. Entsprechend werden dabei dann immer das größte und kleinste Element in der unsortierten Liste gesucht und entsprechend nach vorne oder nach hinten eingesetzt werden. Dadurch kann im Normalfall eine Beschleunigung erreicht werden.

Selection Sort Beispiel

Jetzt schauen wir uns ein auführliches Beispiel eines Standard-Selectionsorts an.

Gegeben sind fünf Spielkarten [7][5][2][9][4] unsortiert in einer Reihe, die  der Größe nach aufsteigend nach dem MinSort-Prinzip geordnet werden sollen. Man sieht dabei im ersten Schritt erstmal alle Karten der Reihe nach an und sucht dann nach der Karte mit dem niedrigsten Wert – in diesem Fall die 2. Die 2 wird dann mit der ersten Stelle des unsortierten Bereichs, also der 7, vertauscht.  Die Karte 2 ist damit auf ihrem richtigen Platz und gilt als fertigsortiert, deshalb wird sie im weiteren Verlauf nicht mehr beachtet. Nun zum zweiten Wert – der 5, welcher mit der 7, der 9 und der 4 verglichen wird. Die 4 ist kleiner als die 5 und wird deshalb wieder mit der 5 vertauscht. Der Vorgang wird mit der der Karte 7 wiederholt, die dann ihren Platz mit der 5 wechselt und zum Schluss werden auch noch die Karten 9 und 7 ausgetauscht. Am Ende erhält man den fertig sortierte Array: [2][4][5][7][9]

Liste.

Im Folgeden wird der Sortiervorgang des Beispiels anhand der einzelnen Durchläufe dargestellt:

[7][5][2][9][4]

[2][5][7][9][4]

[2][4][7][9][5]

[2][4][5][9][7]

[2][4][5][7][9]

Algorithmus

Wir wissen nun also, wie der Sortieralgorithmus funktioniert. Doch was für ein Algorithmus lässt sich daraus jetzt eigentlich ableiten?

Zuerst brauchen wir eine Liste. Diese ist anfangs komplett unsortiert, weswegen der sortierte Bereich zu Beginn als leer gilt. Die Bedingung ist dabei, dass solange der unsortierte Bereich noch ein Element enthält, soll nach dem kleinsten oder dem größten Element im unsortierten Bereich gesucht werden. Sollte ein Element des unsortierten Bereichs kleiner als der Vergleichswert sein, dann wird das passende Element aus dem unsortierten Bereich entfernt und in den Sortierten Bereich an seine richtige Position eingefügt. Am Ende erhalten wir dann eine sortierte Liste.

Hier kannst du dir den theoretischen Aufbau noch einmal genauer ansehen:

Selection Sort Algorithm, Selection Sort Algorithmus
direkt ins Video springen
Selection Sort Algorithm

Selection Sort Pseudocode

Der Selection Sort Pseudocode lässt sich dann beispielsweise so darstellen:

Selectionsort (Liste l)
     For i = 0 to n-2
     Do
          Minimum = i
          For j = i + 1 to n-1
          Do
               If l[Minimum] > l[j] then Minimum = j
                    tmp = l[i]
                    l[i] = l[Minimum]
                    l[Minimum] = tmp

Selection Sort Struktogramm

Zusätzlich kannst du den Pseudocode natürlich auch als Selection Sort-Struktogramm darstellen. Das könnte dann beispielsweise so aussehen:

Selection Sort Struktogramm, Nassi Schneidermann Diagramm
direkt ins Video springen
Selection Sort Struktogramm

Selection Sort Laufzeit

Doch wie sieht es jetzt noch mit der Laufzeitkomplexität aus? Der Sortieralgorithmus ist nämlich ein ziemlich besonderer Fall, denn es sind wie beim Mergesort  keine Unterschiede festzustellen. Die Laufzeit im Selection Sort Worst Case entspricht genau der Komplexität im Best Case. Damit beträgt die Selection Sort Laufzeit immer O(n2). Das hat einen ganz einfachen Grund, denn die Liste wird unabhängig von vorsortierten Daten immer von vorne bis hinten komplett durchlaufen. Deshalb benötigt er  Vergleiche, wovon wir die allgemeine Selection Sort Laufzeit ableiten können.

Selection Sort Java Code

Zum Abschluss zeigen wir dir auch noch ein Beispiel  für einen Quellcode einer Selection Sort Java-Implementierung:

//Liste l, die mit dem Heapsort sortiert werden soll
public class SelectionSort
{ 
private int[] l; 
    // Übernehmen von Referenz auf eine Liste und sortiert sie
    public void sort(int[] anListe)
    {
        l=anListe;
        Sortierung();
    }
    // sortiert doe Liste l mit dem Selectionsort
    private void Sortierung()
    {
        for (int i=0; i
        {
            int pm = PositionMinimum(i);
            swap(pm, i);
        }
    }
// findet die Position der kleinsten Zahl PositionMinimum ab der ersten Position erste Zahl im unsortierten Bereich
    private int PositionMinimum(int ersteZahl)
    {
        int pm = ersteZahl;
        for (int i=ersteZahl+1; i
            if (l[i]
                pm = i;
        return pm;
    }
    // tausche zwei Zahlen in der Liste
    private void swap(int i, int j)
    {
        int tmp=l[i];
        l[i]=l[j];
        l[j]=tmp;
    }
}

Andere Nutzer halten diese Inhalte aus dem Bereich „Theoretische Informatik“ für besonders klausurrelevant

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.