Sortieralgorithmen/ Sortierverfahren im Überblick

Sortieren ist schon immer ein wichtiger Inhalt im Leben und in der Kultur der Menschheit. In dem Märchen "Aschenputtel" muss Aschenputtel Linsen sortieren. Nach dem Schema: "Die Guten ins Töpfchen, die Schlechten ins Kröpfchen“.(1) Auch bei der Programmierung von Anwendungen spielen Sortierverfahren eine wichtige Rolle. Zum Beispiel bei einem Programm, welches Namen nach Anfangsbuchstaben sortieren soll.

Doch was ist sortieren allgemein? Sortieren ist das Auslesen bzw. Ordnen vorgegebener Elemente nach einem bestimmten Schema und die Darstellung des Ergebnisses dieses Vorganges. Listen oder Verzeichnisse können das Ergebnis der Sortierung sein. (2)

Das Wort sortieren stammt aus dem Italienischen, das Italienische jedoch wiederum aus dem Lateinischen. Sortieren kommt von "sortiri" und bedeutet erlesen, auswählen. Im Italienischen wird sortieren mit "sortire" übersetzt. Im Qualitätsmanagement ist eine andere Bezeichnung des Sortierens auch Vollprüfung.

In der Informatik wird versucht, durch optimales Einsetzten von Sortierverfahren möglichst viel Speicher- und Rechenzeit zu sparen. Hierbei hat jedes Sortierverfahren seine Vor- und Nachteile. Manche können zum Beispiel kleine Datenmengen schnell verarbeiten, andere sind eher für große Datenmengen geeignet. Es gibt aber auch unsinnige Sortierverfahren, wie Slow - oder Bogosort, deren Laufzeit sehr lange ist. Bei Bogosort zum Beispiel wird die Zahlenreihe zufällig angeordnet, solange bis diese geordnet ist. Jedes Sortierverfahren hat eine eigene Vorgehensweise, auch wenn sich einige Sortierverfahren ähneln. (3)

In der Programmierung wird zwischen stabilen und unstabilen Sortierverfahren unterschieden. Ein stabiles Sortierverfahren ist dann stabil, wenn eine Datenmenge mehrere gleiche Werte hat, welche hintereinander stehen. Nach der Sortierung müssen die Elemente mit gleichem Wert immer noch in gleicher Reihenfolge hintereinander stehen. Zum Beispiel so: 1,2,9,4,7,6 (die erste), 6 (die zweite) und nach der Sortierung 1,2,4,6 (die erste), 6 (die zweite), 7,9.

Ein weiterer Unterschied ist, ob das Sortierverfahren in-place (in situ) oder out-of-place arbeitet. Ist der Sortieralgorithmus nämlich out-of-place, dann speichert er während des Algorithmus Daten auf einer zweiten Liste, womit mehr Speicherplatz verwendet wird, als bei einem in-place Sortierverfahren welches die Daten "überspeichert". (4)

Doch auch die Laufzeit des Sortierverfahrens ist ein wichtiger Punkt in der Programmierung. Hierbei wird zwischen dem Worst-Case und dem Best-Case unterschieden. Mit Worst-Case wird die schlechteste Laufzeit und mit Best-Case, wie der Name sagt, die beste Laufzeit des Sortierverfahrens bezeichnet.