Sortieralgorithmus

Wenn du deine Klassenliste alphabetisch ordnest, sortierst du. Auch dein Handy sortiert Fotos nach Datum oder Kontakte nach Namen. In der Informatik macht das ein Programm Schritt für Schritt. Genau dafür gibt es Sortieralgorithmen.

Worum geht es beim Sortieren?

Deine Lernziele

• Du verstehst, was ein Sortieralgorithmus ist.
• Du erkennst Eingabe und Ausgabe beim Sortieren.
• Du kannst erklären, warum Computer genaue Sortierschritte brauchen.
• Du unterscheidest einfache und schnelle Sortierideen.

Ein Computer sieht eine Liste nicht so wie du auf einen Blick. Er arbeitet mit einzelnen Schritten. Deshalb braucht er eine klare Vorschrift.

Ein Algorithmus ist eine genaue Schritt-für-Schritt-Anleitung, mit der ein Problem gelöst wird. Ein Sortieralgorithmus ist ein Algorithmus, der Daten in eine gewünschte Reihenfolge bringt.

Die Daten stehen oft in einer Liste. Eine Liste ist eine geordnete Sammlung von Werten, zum Beispiel Zahlen, Namen oder Dateien. Die unsortierte Liste ist die Eingabe. Die sortierte Liste ist die Ausgabe.

Definition

Ein Sortieralgorithmus bringt die Elemente einer Liste nach einer Regel in die richtige Reihenfolge.

Die Regel kann zum Beispiel sein:

• Zahlen von klein nach groß
• Wörter nach dem Alphabet
• Dateien nach Datum
• Punkte in einer Tabelle von hoch nach niedrig

Beispiel

Eingabe: 7, 2, 9, 1

Sortierregel: von klein nach groß

Ausgabe: 1, 2, 7, 9

Merke

Ein Sortieralgorithmus braucht immer eine Sortierregel. Ohne Regel weiß der Computer nicht, was richtig geordnet bedeutet.

Vergleichen und Tauschen

Viele Sortieralgorithmen arbeiten wie beim Kartenordnen. Sie schauen zwei Elemente an und entscheiden: Stehen sie richtig, oder müssen sie getauscht werden?

Ein Vergleich prüft zwei Elemente nach der Sortierregel. Bei Zahlen kann der Computer fragen: Ist 8 größer als 3? Bei Namen kann er fragen: Kommt Anna im Alphabet vor Ben?

Ein Tausch bedeutet: Zwei Elemente wechseln ihre Plätze in der Liste.

Beispiel

Liste: 5, 2, 4

Der Algorithmus vergleicht 5 und 2.

5 ist größer als 2, aber klein soll links stehen. Also werden 5 und 2 getauscht.

Neue Liste: 2, 5, 4

Bei einem vergleichsbasierten Sortieralgorithmus entsteht die Reihenfolge durch solche Vergleiche. Viele bekannte Verfahren gehören dazu, zum Beispiel Bubble Sort, Selection Sort, Insertion Sort, Merge Sort und Quicksort.

Merke

Vergleichsbasiertes Sortieren bedeutet: Der Algorithmus entscheidet durch Paarvergleiche, welches Element vor welchem stehen soll.

Drei einfache Sortierideen

Einfache Sortierverfahren sind gut zum Verstehen. Sie sind bei kleinen Listen okay, werden bei großen Listen aber oft langsam.

Bubble Sort vergleicht immer Nachbarn. Wenn zwei benachbarte Elemente falsch stehen, werden sie getauscht. Große Werte wandern dadurch Schritt für Schritt nach rechts, ähnlich wie Blasen nach oben steigen.

Beispiel

Liste: 4, 1, 3

Vergleiche 4 und 1: falsch, also tauschen. Liste: 1, 4, 3

Vergleiche 4 und 3: falsch, also tauschen. Liste: 1, 3, 4

Nach einem Durchlauf steht die größte Zahl rechts.

Selection Sort sucht zuerst das kleinste Element und setzt es nach vorne. Danach sucht er im Rest wieder das kleinste Element. So wächst links der sortierte Teil.

Beispiel

Liste: 4, 2, 6, 1, 5

Kleinstes Element ist 1. Es kommt nach vorne. Liste: 1, 2, 6, 4, 5

Jetzt ist links die 1 fest sortiert. Im Rest ist noch nicht alles richtig.

Nächstes kleinstes Element im Rest ist 2. Es bleibt an seiner Stelle. Dann wird im übrigen Rest weitergesucht.

Insertion Sort baut eine sortierte Teilliste auf. Ein neues Element wird an die passende Stelle eingefügt. Das kennst du, wenn du Spielkarten auf der Hand sortierst.

Beispiel

Du hast schon sortiert: 2, 5, 9

Neue Karte: 6

6 gehört zwischen 5 und 9.

Ergebnis: 2, 5, 6, 9

Merke

Bubble Sort, Selection Sort und Insertion Sort zeigen die Grundideen gut. Für sehr große Listen sind sie meistens nicht die beste Wahl.

Schneller sortieren mit Teilen und Zusammenfügen

Bei großen Datenmengen brauchen Programme oft bessere Strategien. Zwei wichtige Verfahren heißen Merge Sort und Quicksort. Beide nutzen die Idee: Ein großes Problem wird in kleinere Probleme zerlegt.

Teile und herrsche ist eine Strategie, bei der ein Problem in kleinere Teilprobleme zerlegt wird. Die Teilprobleme werden gelöst. Danach entsteht daraus die Gesamtlösung.

Bei Merge Sort wird die Liste immer weiter geteilt, bis sehr kleine Listen entstehen. Eine Liste mit nur einem Element ist schon sortiert. Danach werden die kleinen sortierten Listen wieder geordnet zusammengefügt.

Beispiel

Start: 8, 3, 5, 1

Teilen: 8, 3 und 5, 1

Weiter teilen: 8 und 3 und 5 und 1

Zusammenfügen: 3, 8 und 1, 5

Noch einmal zusammenfügen: 1, 3, 5, 8

Bei Quicksort wird ein Vergleichswert gewählt. Dieser Wert heißt Pivot. Ein Pivot ist ein ausgewähltes Element, an dem die Liste grob aufgeteilt wird. Kleinere Werte kommen auf eine Seite, größere Werte auf die andere Seite. Danach werden die Teilbereiche wieder genauso behandelt.

Beispiel

Liste: 7, 2, 9, 4, 1

Pivot: 4

Kleiner als 4: 2, 1

Pivot: 4

Größer als 4: 7, 9

Danach werden die linken und rechten Teile weiter sortiert.

Gut zu wissen

Merge Sort ist oft gut vorhersagbar, braucht aber zusätzlichen Speicher für das Zusammenfügen.

Quicksort ist in der Praxis häufig sehr schnell. Bei ungünstiger Pivot-Wahl kann es aber deutlich langsamer werden.

Laufzeit und Speicherplatz

Nicht jeder Sortieralgorithmus ist gleich schnell. Wichtig ist nicht nur, wie lange er bei einer kleinen Liste braucht. Wichtig ist, wie stark die Arbeit wächst, wenn die Liste größer wird.

Die Zeitkomplexität beschreibt, wie die Anzahl der Arbeitsschritte mit der Eingabegröße wächst. Die Eingabegröße wird oft mit \(n\) bezeichnet. \(n\) ist die Anzahl der Elemente in der Liste.

Die O-Notation beschreibt dieses Wachstum grob. Sie schaut nicht auf Sekunden, sondern auf die Größenordnung.

Definition

Die Zeitkomplexität beschreibt, wie stark die Laufzeit eines Algorithmus wächst, wenn die Eingabe größer wird.

Die O-Notation gibt dafür eine vereinfachte Wachstumsform an, zum Beispiel \(O(n)\), \(O(n \log n)\) oder \(O(n^2)\).

Beispiel

Stell dir vor, du sortierst 4 Zahlen.

Ein sehr günstiges Verfahren braucht vielleicht ungefähr eine Arbeit pro Zahl. Dann wächst die Arbeit etwa wie \(O(n)\).

Ein langsameres Verfahren vergleicht viele Zahlenpaare. Bei 4 Zahlen gibt es schon mehrere mögliche Paarvergleiche. Bei 8 Zahlen werden es viel mehr. Dieses starke Wachstum passt eher zu \(O(n^2)\).

Darum kann eine Methode bei 4 Zahlen noch harmlos wirken, bei 4000 Zahlen aber sehr langsam werden.

Die Platzkomplexität beschreibt, wie viel zusätzlicher Speicher ein Algorithmus braucht. Zusätzlicher Speicher meint nicht die ursprüngliche Liste selbst, sondern Hilfslisten, Zwischenspeicher oder Stapel für Zwischenschritte.

Ein Algorithmus arbeitet in-place, wenn er nur sehr wenig zusätzlichen Speicher braucht. Er sortiert also hauptsächlich in der vorhandenen Liste.

Beispiel

Selection Sort kann in derselben Liste sortieren. Er braucht nur wenige Hilfsvariablen. Das ist in-place.

Merge Sort braucht beim Zusammenfügen oft zusätzlichen Platz für Hilfslisten. Das ist meist nicht in-place.

Merke

Für kleine Listen ist fast jedes einfache Verfahren schnell genug. Für große Listen zählt die Zeitkomplexität stark.

Stabilität und besondere Sortierarten

Manchmal haben zwei Elemente denselben Sortierwert. Dann ist wichtig, ob ihre alte Reihenfolge erhalten bleibt.

Ein Sortierschlüssel ist der Wert, nach dem sortiert wird. Bei Personen kann der Sortierschlüssel zum Beispiel der Nachname, das Alter oder die Punktzahl sein.

Ein Sortieralgorithmus heißt stabil, wenn Elemente mit gleichem Sortierschlüssel ihre bisherige Reihenfolge behalten. Er heißt instabil, wenn diese Reihenfolge nicht garantiert wird.

Beispiel

Ausgangsliste ist nach Vornamen sortiert:

Anna Müller
Ben Schneider
Clara Müller

Jetzt sortierst du nach Nachnamen.

Bei stabiler Sortierung bleiben Anna Müller und Clara Müller in dieser Reihenfolge, weil beide denselben Nachnamen haben und Anna vorher vor Clara stand.

Merke

Stabilität ist besonders nützlich beim mehrstufigen Sortieren. Du sortierst zuerst nach dem weniger wichtigen Merkmal und danach stabil nach dem wichtigsten Merkmal. Dann bleibt die Reihenfolge innerhalb gleicher Hauptwerte sinnvoll erhalten.

Ein nicht-vergleichsbasierter Sortieralgorithmus sortiert nicht durch direkte Paarvergleiche wie kleiner, größer oder gleich. Er nutzt andere Eigenschaften der Daten, zum Beispiel bekannte Zahlenbereiche oder einzelne Ziffernstellen.

Beispiel

Counting Sort eignet sich, wenn die möglichen Werte überschaubar sind.

Liste: 3, 1, 2, 3, 1

Zähle: 1 kommt 2-mal vor 2 kommt 1-mal vor 3 kommt 2-mal vor

Schreibe daraus: 1, 1, 2, 3, 3

Merke

Vergleichsbasierte Verfahren fragen: Welches von zwei Elementen kommt zuerst? Nicht-vergleichsbasierte Verfahren nutzen Zusatzwissen über die Werte, zum Beispiel einen kleinen bekannten Zahlenbereich.

Solche Verfahren können sehr schnell sein, passen aber nicht für jede Datenart. Wenn der Wertebereich riesig oder unbekannt ist, brauchen sie oft zu viel Speicher oder sind unpraktisch.

Zusammenfassung

Ein Sortieralgorithmus ist eine genaue Anleitung, die eine Liste nach einer Regel ordnet. Die Eingabe ist die unsortierte Liste. Die Ausgabe ist die sortierte Liste.

Viele Verfahren sortieren durch Vergleiche und Tausche. Bubble Sort, Selection Sort und Insertion Sort sind einfache Grundideen. Merge Sort und Quicksort zeigen, wie man große Listen durch Aufteilen schneller sortieren kann.

Zeitkomplexität sagt dir, wie stark die Arbeit bei größeren Listen wächst. Platzkomplexität sagt dir, wie viel zusätzlicher Speicher nötig ist. Stabilität ist wichtig, wenn gleiche Sortierschlüssel ihre alte Reihenfolge behalten sollen.