Selectionsort

Stell Dir vor, Du hast einen Satz an Spielkarten, die Du der Größe nach sortieren willst. Wie würdest Du dabei klassischerweise beginnen? Genau – Du suchst Dir zunächst entweder die kleinste oder die größte Karte heraus, machst dann mit der darauffolgenden Karte weiter und das Ganze wiederholst Du bist alle Spielkarten richtig sortiert sind. 

Selectionsort Selectionsort

Erstelle Lernmaterialien über Selectionsort mit unserer kostenlosen Lern-App!

  • Sofortiger Zugriff auf Millionen von Lernmaterialien
  • Karteikarten, Notizen, Übungsprüfungen und mehr
  • Alles, was du brauchst, um bei deinen Prüfungen zu glänzen
Kostenlos anmelden
Inhaltsverzeichnis
Inhaltsangabe

    So ähnlich funktioniert auch das Sortierverfahren Selection Sort. Was der jedoch noch etwas anders macht und wie effizient der Algorithmus wirklich ist, das erfährst Du hier.

    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.

    Der Begriff Selection Sort setzt sich aus den englischen Wörtern selection ("Auswahl") und sort ("sortieren") zusammen. Deswegen wird bei dem Algorithmus auch häufig von "Sortieren durch Auswahl" gesprochen.

    Selection Sort Definition

    Selection Sort ist ein Sortieralgorithmus, der wiederholt nach dem kleinsten oder größtem Element in einem Array sucht und dieses aus dem unsortierten Teil an den Anfang des Arrays verschiebt.

    Anstatt von Selection Sort kann übrigens auch von Exchange Sort oder Selectsort die Rede sein.

    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.

    IterationenDurchführungSortiertUnsortiert
    Schritt 1Teile das Array gedanklich in einen sortierten und einen unsortierten Teil ein. Der sortierte Teil ist am Anfang noch leer. 5 28497
    Schritt 2 Durchsuche jetzt das unsortierte Array nach dem kleinsten Element. Du beginnst dabei mit der 5, dann wird das Array schrittweise durchgegangen. An der zweiten Stelle findest Du mit der 2 bereits eine kleinere Zahl, gehe trotzdem noch das restliche Array durch und schaue, ob es eine noch kleinere Zahl gibt. Das ist in diesem Beispiel nicht der Fall. Vertausche also die 2 mit der 5 und verschiebe die Grenze zwischen der sortierten und der unsortierten Seite um eine Stelle nach rechts.258497
    Schritt 3Suche nun wieder im unsortierten Teil nach dem kleinsten Element (4) und vertausche diese Zahl mit der an der zweiten Stelle (5). Schiebe das Ganze danach wieder einen Schritt nach links.248597
    Schritt 4Als Nächstes müssen die 5 und die 8 miteinander vertauscht werden. Verschiebe auch danach wieder die Grenze um einen Schritt nach rechts.245897
    Schritt 5Das nächste kleinste Element ist die 7. Vertausche diese also mit der 8 und verschiebe die Grenze wieder nach rechts.245798
    Schritt 6Tausche nun noch die 8 und die 9 miteinander und verschiebe erneut die Grenze.245789
    EndeDas letzte Element ist automatisch das Größte, vorausgesetzt Du hast alles richtig gemacht. Der Algorithmus ist somit beendet und das Array ist vollständig sortiert.245789

    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.

    Das Ganze läuft übrigens genauso ab, wenn Du absteigend, beginnend beim größten Element, sortieren willst. Nur, dass Du dann immer nach dem jeweils größtem Element im unsortierten Teil schaust und das an den Anfang verschiebst.

    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(n2). Das liegt daran, dass der Algorithmus zwei ineinander verschachtelte Schleifen enthält.

    Falls Dir der Unterschied von einem einfachen zu einem effizienten Sortieralgorithmus nicht klar sein sollte, findest Du dazu mehr in der Erklärung zu den Sortieralgorithmen.

    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(n2).

    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!

    Es ist jedoch möglich, Selection Sort stabil zu implementieren.

    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(n2). Die Platzkomplexität beträgt bei der rekursiven Variante allerdings O(n) statt O(1).

    Zur Erinnerung: O(1) ist ein konstanter Aufwand, das heißt, der Aufwand ist unabhängig von der Anzahl der Eingabeelemente. O(n) ist hingegen ein linearer Aufwand – der Aufwand wächst also linear mit der Anzahl der Eingabeelemente an.

    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.

    Alles in allem gilt der Sortieralgorithmus also als nicht parallelisierbar!

    Selection Sort Zusammenfassung

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

    Best-CaseAverage-CaseWorst-CasePlatz-komplexitätStabiles Verfahrenvergleichs-basiertIn-PlaceParallelisier-barkeititerativ/rekursiv
    O(n2)O(n2)O(n2)O(1)NeinJaJazu Teilen parallelisierbarBeides möglich

    Selection Sort Vorteile – Nachteile

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

    VorteileNachteile
    Leicht verständlichArbeitet ineffizient
    Einfach zu implementieren

    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.

    "Kosten" meint dabei die Effizienz des Algorithmus, also wie viele Durchläufe es braucht, bis eine Datenmenge vollständig sortiert ist.

    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

    "temp" ist übrigens die Bezeichnung für eine Hilfsvariable.

    Selectionsort – Das Wichtigste

    • Selection Sort Definition: Der Selection Sort ist ein Sortieralgorithmus, der wiederholt nach dem kleinsten/größtem Element einer Datenmenge sucht und dieses aus dem unsortierten Teil an den Anfang des Arrays verschiebt.
    • Selection Sort Komplexität: O(n2) = quadratisch ansteigende Laufzeit
    • Selection Sort Platzkomplexität:O(1) = konstanter Aufwand
      • Algorithmus arbeitet in-place
    • Der Selection Sort Algorithmus ist:
      • nicht stabil = instabil,
      • vergleichsbasiert,
      • iterativ sowie rekursiv implementierbar,
      • und nicht parallelisierbar.
    • Selection Sort Anwendung, wenn:
      • kleine Datenmengen sortiert werden sollen.
      • die Überprüfung aller Elemente verpflichtend ist.
      • die "Kosten" für den Austausch keine Rolle spielen.

    Nachweise

    1. Happycoders.eu: Selection Sort – Algorithmus, Quellcode, Zeitkomplexität. (18.10.2022)
    2. Geeksforgeeks.org: Selection Sort Algorithm. (18.10.2022)
    Häufig gestellte Fragen zum Thema Selectionsort

    Wie funktioniert der Selection Sort? 

    Beim Selection Sort wird wiederholt nach dem kleinsten oder größten Element einer unsortierten Datenmenge gesucht. Das jeweilige Element wird dann immer mit dem ersten Element des unsortierten Abschnitts vertauscht. 

    Warum ist Selection Sort nicht stabil? 

    Der Selection Sort ist nicht stabil, da das Vertauschen von Elementen im unsortierten Abschnitt die ursprüngliche Reihenfolge durcheinander bringen kann. 

    Ist Selection Sort rekursiv? 

    Der Selection Sort kann rekursiv implementiert werden. Die Zeitkomplexität bleibt dabei O(n2), die Platzkomplexität beträgt dann jedoch O(n). 

    Wann benutzt man Selection Sort? 

    Der Selection Sort wird vor allem bei kleineren Datenmengen verwendet, da es bei größeren zu Problemen mit der Laufzeit kommen kann. 

    Teste dein Wissen mit Multiple-Choice-Karteikarten

    Wahr oder falschBeim Selection Sort handelt es sich um einen Algorithmus, der Datenmengen durch Auswahl sortiert. 

    Wie kann der Selection Sort noch genannt werden?

    Wie lautet die Zeitkomplexität des Selection Sort?

    Weiter
    1
    Über StudySmarter

    StudySmarter ist ein weltweit anerkanntes Bildungstechnologie-Unternehmen, das eine ganzheitliche Lernplattform für Schüler und Studenten aller Altersstufen und Bildungsniveaus bietet. Unsere Plattform unterstützt das Lernen in einer breiten Palette von Fächern, einschließlich MINT, Sozialwissenschaften und Sprachen, und hilft den Schülern auch, weltweit verschiedene Tests und Prüfungen wie GCSE, A Level, SAT, ACT, Abitur und mehr erfolgreich zu meistern. Wir bieten eine umfangreiche Bibliothek von Lernmaterialien, einschließlich interaktiver Karteikarten, umfassender Lehrbuchlösungen und detaillierter Erklärungen. Die fortschrittliche Technologie und Werkzeuge, die wir zur Verfügung stellen, helfen Schülern, ihre eigenen Lernmaterialien zu erstellen. Die Inhalte von StudySmarter sind nicht nur von Experten geprüft, sondern werden auch regelmäßig aktualisiert, um Genauigkeit und Relevanz zu gewährleisten.

    Erfahre mehr
    StudySmarter Redaktionsteam

    Team Selectionsort Lehrer

    • 11 Minuten Lesezeit
    • Geprüft vom StudySmarter Redaktionsteam
    Erklärung speichern

    Lerne jederzeit. Lerne überall. Auf allen Geräten.

    Kostenfrei loslegen

    Melde dich an für Notizen & Bearbeitung. 100% for free.

    Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

    Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

    • Karteikarten & Quizze
    • KI-Lernassistent
    • Lernplaner
    • Probeklausuren
    • Intelligente Notizen
    Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!