Sortieren

Einführung

Ein übliches Problem in der Informatik  ist es, Daten zu sortieren. Wer das Sortieren verstanden hat, dem wird es nicht schwerfallen, andere Algorithmen zu verstehen. Das Sortieren könnte man sozusagen auch als »Basics für Algorithmen« bezeichnen.

Primär geht es darum, die einzelnen Sortierverfahren näherzubringen, speziell deren Funktionen. Die Implementierung ist zumeist problemabhängig und richtet sich nach der Art der Daten, die es zu sortieren gilt (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm).Es gibt unterschiedliche Algorithmen für ein gegebenes Problem und so gibt es  verschiedene Sortierverfahren. Jeder Algorithmus arbeitet unterschiedlich effizient, um ein Problem zu lösen. Die Zeitkomplexität eines Sortieralgorithmus gibt an, wie viele Operationen nötig sind, um einen Sortiervorgang abzuschließen. Bei gegebenen Hardwareausstattung lässt sich also messen, wie lange ein Sortiervorgang dauert.

Platzkomplexität – In-place

 Zusätzlich wird die Platzkomplexität eines Sortierverfahrens betrachtet. Hier wird analysiert, ob und wie viel zusätzlicher Speicher für den Sortiervorgang an sich benötigt wird. Bei in-Place wird nur eine konstante Menge an zusätzlichem Speicher benötigt z.B. Hilfsvariablen für den Dreieckstausch. Bei out-of-place wird eine dynamische Anzahl von zusätzlichem Speicher benötigt die abhängig von der Eingabegröße ist. 

Vergleichsbasierte Verfahren

Sortierverfahren können sich allgemein durch die Basis der Arbeitsweise unterscheiden. Zum einen können Sortieralgorithmen vergleichsbasiert arbeiten oder eben nicht. Das heißt, dass ein Teil der Sortieralgorithmen Vergleiche von Elementen der Liste verwendet, um die Elemente entsprechend in die richtige Reihenfolge zu tauschen. Beim nicht vergleichsbasierten Verfahren liegt der Fokus auf der konditionierten Eingabe.  Im Folgenden werden die vergleichsbasierten sortierverfahren behandelt.

Stabilität

Zusätzliche kann zwischen stabilem und instabilem Verfahren unterschieden werden. Bei stabile Verfahren bleibt die Reihenfolge der Datensätze gleich, deren Sortierschlüssel auch gleich sind. Angenommen man möchte in einem Verein die bereits alphabetisch geordnete Mitglieder nach dem Geburtsdatum sortieren. Stabile Verfahren sorgen dafür, dass die Mitglieder mit gleichem Geburtsdatum weiterhin noch nach der alphabetischen Reihenfolge sortiert bleiben. Das Verfahren sortiert in erster Priorität nach dem Geburtsdatum und in zweiter Priorität  nach alphabetische Reihenfolge.