Mit Google fortfahren
Sortieralgorithmus: Verfahren einfach vergleichen
Ein Sortieralgorithmus bringt Daten nach einer festgelegten Ordnung in eine Reihenfolge. Dabei dürfen keine Elemente verloren gehen oder neu hinzukommen. Du lernst hier, wie Bubble-, Selection- und Insertionsort arbeiten, woran du ihren Fortschritt erkennst und wie du ihren Aufwand vergleichst.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Was muss ein Sortieralgorithmus leisten?
Stell dir eine ungeordnete Liste vor:
[4, 2, 3, 1]
Für eine aufsteigende Ordnung soll daraus [1, 2, 3, 4] werden. Ein korrektes Ergebnis erfüllt zwei Bedingungen:
- Die Werte stehen in der verlangten Reihenfolge.
- Das Ergebnis enthält genau dieselben Werte wie die Eingabe, auch wenn ein Wert mehrfach vorkommt.
Sortierschlüssel
Der Sortierschlüssel ist die Eigenschaft, nach der geordnet wird. Bei Zahlen kann der Zahlenwert der Schlüssel sein. Bei Personendaten könnte es das Geburtsjahr sein. Mehrere Datensätze können denselben Schlüssel besitzen.
Die drei Verfahren auf dieser Seite sind vergleichsbasiert: Sie bestimmen die Reihenfolge, indem sie Schlüssel miteinander vergleichen. Sie unterscheiden sich vor allem darin, welcher Teil der Liste bereits als sicher sortiert gilt.
Beobachte beim Ausführen eines Sortierverfahrens immer drei Dinge: Was wird verglichen? Was wird bewegt? Welcher Bereich ist danach sicher sortiert?
Wie lässt Bubblesort große Werte nach rechts steigen?
Bubblesort vergleicht benachbarte Werte von links nach rechts. Ist der linke Wert größer, werden beide vertauscht. Nach einer vollständigen Runde steht der größte noch nicht festgelegte Wert ganz rechts.
Wir sortieren [4, 2, 3, 1] aufsteigend.
Runde 1:
4und2: tauschen →[2, 4, 3, 1]4und3: tauschen →[2, 3, 4, 1]4und1: tauschen →[2, 3, 1, 4]
Nun steht 4 endgültig rechts.
Runde 2: Nur der Bereich links von 4 ist noch offen.
2und3: nicht tauschen3und1: tauschen →[2, 1, 3, 4]
Runde 3:
2und1: tauschen →[1, 2, 3, 4]
Eine weitere Prüfrunde ohne Tausch würde bestätigen, dass die ganze Liste sortiert ist. Eine Umsetzung kann dann früh abbrechen.
Der entscheidende Fortschritt lautet: Nach jeder vollständigen Runde wächst rechts der Bereich, dessen Werte bereits an ihrer endgültigen Position stehen.
Wie wählt Selectionsort jeweils das Minimum aus?
Selectionsort teilt die Liste in einen sortierten linken und einen unsortierten rechten Bereich. In jeder Runde sucht das Verfahren das kleinste Element des unsortierten Bereichs und tauscht es an dessen erste Position.
Wir beginnen wieder mit [4, 2, 3, 1].
- Im gesamten Bereich ist
1das Minimum. Tausch mit4→[1, 2, 3, 4]. - Im Rest
[2, 3, 4]ist2bereits vorn. Es muss kein wertverändernder Tausch stattfinden. - Im Rest
[3, 4]ist3bereits vorn.
Nach Runde 1 steht das kleinste Element sicher links. Nach Runde 2 stehen die zwei kleinsten Elemente sortiert links. Dieses Muster setzt sich fort.
Diese Aussage über den wachsenden linken Bereich ist eine Schleifeninvariante. Sie beschreibt einen Zustand, der bei jeder passend betrachteten Runde erhalten bleibt, und hilft, die Korrektheit des Verfahrens zu begründen.
Schleifeninvariante
Eine Schleifeninvariante ist eine Aussage, die bei jeder Wiederholung einer Schleife erhalten bleibt. Bei Selectionsort lautet sie sinngemäß: Links stehen bereits die kleinsten Werte in richtiger Reihenfolge.
Wie fügt Insertionsort einen Wert passend ein?
Insertionsort hält links einen sortierten Bereich. Das nächste Element rechts davon wird zwischengespeichert. Größere Werte im sortierten Bereich werden nach rechts verschoben, bis die passende Lücke erreicht ist.
Auch hier ist die Eingabe [4, 2, 3, 1].
[4]gilt als sortiert. Für2wird4nach rechts verschoben;2kommt in die freie Lücke →[2, 4, 3, 1].- Für
3wird4nach rechts verschoben. Weil2nicht größer als3ist, kommt3dahinter →[2, 3, 4, 1]. - Für
1werden4,3und2nach rechts verschoben.1kommt an den Anfang →[1, 2, 3, 4].
Nach jedem Einfügeschritt ist der linke Bereich wieder vollständig sortiert.
Insertionsort profitiert von Vorsortierung: Steht das nächste Element bereits richtig, sind nur wenige Vergleiche und keine langen Verschiebungen nötig.
Worin unterscheiden sich Aufwand, Stabilität und Speicher?
Für den Aufwand zählt man zum Beispiel Vergleiche und Bewegungen. Bei wachsendem n beschreibt die Laufzeitklasse, wie stark der Aufwand wächst.
| Verfahren | Sortierter Bereich wächst | Best Case | Worst Case | Vorsortierung hilft |
|---|---|---|---|---|
| Bubblesort mit frühem Abbruch | rechts | $\Theta(n)$ | $\Theta(n^2)$ | ja |
| Selectionsort | links | $\Theta(n^2)$ | $\Theta(n^2)$ | bei der Zahl der Vergleiche nein |
| Insertionsort | links | $\Theta(n)$ | $\Theta(n^2)$ | ja |
$\Theta(n)$ bedeutet hier: Der Aufwand wächst in derselben Größenordnung wie die Anzahl der Elemente. $\Theta(n^2)$ bedeutet quadratisches Wachstum. Verdoppelt sich n, kann der maßgebliche Aufwand ungefähr auf das Vierfache wachsen.
Warum entsteht bei den quadratischen Fällen eine Dreieckssumme? In aufeinanderfolgenden Runden werden höchstens n−1, dann n−2 und so weiter bis 1 Vergleiche benötigt:
$$1+2+\dots+(n-1)=\frac{n(n-1)}{2}$$
Für n = 7 sind das 7 · 6 : 2 = 21 Vergleiche.
Stabilität
Ein Sortierverfahren ist stabil, wenn Datensätze mit gleichem Sortierschlüssel ihre relative Reihenfolge behalten. Bubblesort ist stabil, wenn nur bei „links größer als rechts“ getauscht wird. Insertionsort ist stabil, wenn nur echt größere Werte verschoben werden. Selectionsort garantiert keine stabile Reihenfolge.
Beispiel: Eine Mitgliederliste ist zunächst alphabetisch geordnet und wird stabil nach Geburtsjahr sortiert. Personen desselben Jahrgangs bleiben dann untereinander alphabetisch geordnet.
Alle drei hier beschriebenen Verfahren können in-place arbeiten: Ihr zusätzlicher Speicherbedarf bleibt unabhängig von der Länge der Eingabe gering und konstant.
Vertiefung: Warum gibt es schnellere Vergleichsverfahren?
Im Modell des vergleichsbasierten Sortierens benötigt jeder Algorithmus im schlechtesten Fall mindestens eine Größenordnung von $\Omega(n\log n)$ Vergleichen. Die drei einfachen Verfahren benötigen im Worst Case dagegen $\Theta(n^2)$. Andere Verfahren können für große Datenmengen deshalb deutlich günstiger skalieren.
Wie wählst du ein passendes einfaches Verfahren?
Es gibt nicht unabhängig von der Situation „den besten“ Algorithmus. Prüfe stattdessen:
- Eingabe: Ist sie kurz oder schon fast sortiert?
- Ziel: Muss die Reihenfolge gleicher Schlüssel erhalten bleiben?
- Kosten: Sind viele Vergleiche oder viele Datenbewegungen besonders teuer?
- Größe: Reicht ein einfaches quadratisches Verfahren aus, oder ist besseres Wachstum nötig?
Selectionsort führt immer quadratisch viele Minimumvergleiche aus, kann aber in einer Variante auf höchstens n−1 wertverändernde Tausche kommen. Bubblesort bewegt Werte dagegen durch viele Nachbartausche. Insertionsort verschiebt beim Einfügen nur die Werte, die im Weg stehen.
Deine Anwendung
Sortiere [5, 3, 4, 1] mit Insertionsort. Notiere nach jedem Einfügeschritt den sortierten linken Bereich. Entscheide danach, ob die Eingabe bereits stark vorsortiert war.
Lösung:
- Start:
[5] 3einfügen:[3, 5]→ Gesamtfolge[3, 5, 4, 1]4einfügen:[3, 4, 5]→ Gesamtfolge[3, 4, 5, 1]1einfügen:[1, 3, 4, 5]
Die Eingabe war nur teilweise vorsortiert. Besonders das letzte Element 1 verursacht viele Verschiebungen, weil es vor alle bisherigen Werte gehört.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Sortieralgorithmus
- Korrektes Ergebnis
- Reihenfolge stimmt
- Elemente und Häufigkeiten bleiben erhalten
- Bubblesort
- Nachbarvergleiche
- sicherer Bereich rechts
- Selectionsort
- Restminimum wählen
- sicherer Bereich links
- Insertionsort
- in linken Bereich einfügen
- nutzt Vorsortierung
- Auswahlkriterien
- Laufzeit und Bewegungen
- Stabilität und Speicher
- Korrektes Ergebnis