Algorithmen und Datenstrukturen in C/ Sortieren
Was ist mit Sortieren gemeint?
BearbeitenSortieren 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?
BearbeitenEs 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
BearbeitenMan 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