Algorithmen und Datenstrukturen in C/ Sortieren

Was ist mit Sortieren gemeint?

Bearbeiten

Sortieren meint im Zusammenhang mit Algorithmen, Elemente einer Liste, eines Feldes etc. zu Ordnen.

Grundvoraussetzung dafür ist, dass sich die Schlüssel der Elemente in eine Reihenfolge bringen lassen. Das heißt, dass zwischen zwei Elementen genau eine Beziehung <, > oder = wahr sein muss. Es muss also zwischen allen Elementen eine Ordnungsrelation möglich sein.

Die Elemente werden also in eine Reihenfolge E1   E2   E3... gebracht.


Warum verschiedene Sortieralgorithmen?

Bearbeiten

Es gibt mehrere Sortieralgorithmen, von denen einige in diesem Wikibook vorgestellt werden. Das Ergebnis ist bei allen das gleiche: Eine sortierte Menge von Elementen.

Allerdings haben alle Algorithmen Vor- und Nachteile, je nachdem was sortiert werden soll. Zum Beispiel haben einige zwar eine lange Laufzeit, sind aber mit wenig Arbeit bei der Programmierung verbunden, wie Bubblesort. Bei einer geringen Datenmenge empfiehlt es sich also, einen solchen Algorithmus zu wählen.

Einteilung der Sortieralgorithmen

Bearbeiten

Man kann die Soriteralgorithmen nach verschiedenen Kriterien unterteilen:

  • Elementare und verbesserte Sortierverfahren
  • Sortierverfahren die inplace arbeiten und welche die dies nicht tun.
  • Stabile und nicht stabile Sortierverfahren