StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
Americas
Europe
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. So ähnlich funktioniert auch das Sortierverfahren Selection…
Entdecke über 200 Millionen kostenlose Materialien in unserer App
Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken
Jetzt kostenlos anmeldenStell 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.
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.
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 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.
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.
Iterationen | Durchführung | Sortiert | Unsortiert | ||||||||||
Schritt 1 | Teile das Array gedanklich in einen sortierten und einen unsortierten Teil ein. Der sortierte Teil ist am Anfang noch leer. | 5 | 2 | 8 | 4 | 9 | 7 | ||||||
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. | 2 | 5 | 8 | 4 | 9 | 7 | ||||||
Schritt 3 | Suche 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. | 2 | 4 | 8 | 5 | 9 | 7 | ||||||
Schritt 4 | Als Nächstes müssen die 5 und die 8 miteinander vertauscht werden. Verschiebe auch danach wieder die Grenze um einen Schritt nach rechts. | 2 | 4 | 5 | 8 | 9 | 7 | ||||||
Schritt 5 | Das nächste kleinste Element ist die 7. Vertausche diese also mit der 8 und verschiebe die Grenze wieder nach rechts. | 2 | 4 | 5 | 7 | 9 | 8 | ||||||
Schritt 6 | Tausche nun noch die 8 und die 9 miteinander und verschiebe erneut die Grenze. | 2 | 4 | 5 | 7 | 8 | 9 | ||||||
Ende | Das 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. | 2 | 4 | 5 | 7 | 8 | 9 |
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.
Noch mal kurz und knapp zusammengefasst, wie der Algorithmus abläuft, wenn aufsteigend beginnend beim kleinsten Element sortiert werden soll:
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).
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).
In den nächsten Abschnitten werden noch weitere wichtige Begrifflichkeiten rund um das Sortierverfahren Selection Sort erklärt. Folgende Begriffe werden dabei besprochen:
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.
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 ist ein vergleichsbasierter Sortieralgorithmus. Das heißt, der Algorithmus vergleicht immer zwei Elemente eines Datensatzes miteinander auf ein bestimmtes Kriterium.
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 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!
Was solltest Du bisher gelernt haben? In der nachfolgenden Übersicht findest Du die wichtigsten Aspekte des Selection Sort noch einmal zusammengefasst.
Best-Case | Average-Case | Worst-Case | Platz-komplexität | Stabiles Verfahren | vergleichs-basiert | In-Place | Parallelisier-barkeit | iterativ/rekursiv |
O(n2) | O(n2) | O(n2) | O(1) | Nein | Ja | Ja | zu Teilen parallelisierbar | Beides möglich |
Da Selection Sort nicht der einzige existierende Sortieralgorithmus ist, sollte klar sein, dass der Algorithmus verschiedene Vor- und Nachteile hat.
Vorteile | Nachteile |
Leicht verständlich | Arbeitet 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.
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:
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]).
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.
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.
Der Selection Sort ist nicht stabil, da das Vertauschen von Elementen im unsortierten Abschnitt die ursprüngliche Reihenfolge durcheinander bringen kann.
Der Selection Sort kann rekursiv implementiert werden. Die Zeitkomplexität bleibt dabei O(n2), die Platzkomplexität beträgt dann jedoch O(n).
Der Selection Sort wird vor allem bei kleineren Datenmengen verwendet, da es bei größeren zu Problemen mit der Laufzeit kommen kann.
Wie möchtest du den Inhalt lernen?
94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmelden94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmeldenWie möchtest du den Inhalt lernen?
Kostenloser informatik Spickzettel
Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!
Sei rechtzeitig vorbereitet für deine Prüfungen.
Teste dein Wissen mit spielerischen Quizzes.
Erstelle und finde Karteikarten in Rekordzeit.
Erstelle die schönsten Notizen schneller als je zuvor.
Hab all deine Lermaterialien an einem Ort.
Lade unzählige Dokumente hoch und habe sie immer dabei.
Kenne deine Schwächen und Stärken.
Ziele Setze dir individuelle Ziele und sammle Punkte.
Nie wieder prokrastinieren mit unseren Lernerinnerungen.
Sammle Punkte und erreiche neue Levels beim Lernen.
Lass dir Karteikarten automatisch erstellen.
Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.
Melde dich an für Notizen & Bearbeitung. 100% for free.