
Wozu sind Sortieralgorithmen gut??
|
 |

Man kann generell sagen,daß Sortieren vorwiegend dem Beschleunigen des
Suchens dient. Beispiele für sortierte Informationsmengen sind Lexika, Tabellen,
Adressbücher, Kataloge usw.
|
 |

Einteilung der Algorithmen
|
 |

Die wichtigste Eigenschaft von Sortieralgorithmen ist natürlich die
Geschwindigkeit, die in der Datenverarbeitung eine sehr hohe Rolle spielt.
Weiters ist der zusätzliche Speicherbedarf der Methode von entscheidender
Bedeutung, da dieser den Einsatz eines Verfahrens sehr einschränken kann.
- Laufzeit:
Der wichtigste Parameter von Sortieralgorithmen ist natürlich die benötigte
Laufzeit.Die einfachsten Sortier-Methoden sind in ihrem Laufzeitverhalten
proportional N² (N = Anzahl der Elemente). Wenn die Datenbestände nicht allzu
groß sind (bis etwa 500 Elemente), ist es meist effizienter einen einfachen
Algorithmus zu implementieren.
Für größere Datenmengen kommen spezielle Verfahren zum Einsatz deren Laufzeit
proportional zu N*log(N) ist. (keine Sortiermethode kommt mit weniger als
N*log(N) Vergleichen aus).
- Speicherbedarf:
Anhand des benötigten Speicherbedarfs lassen sich die Methoden in drei
Gruppen aufteilen:
- kein Zusätzlicher Speicherbedarf
Diese Verfahren benötigen maximal einen kleinen Stapel oder eine kleine
Tabelle zur Sortierung.
- verkettete Listen
Solche Algorithmen verwenden verkettete Listen zur Sortierung und benötigen
somit N zusätzliche Pointer (meist Worte) als Listenzeiger.
- Stabilität
Ein Sortierverfahren wird stabil genannt, wenn es die relative Reihenfolge
gleicher Schlüssel in einer Datei beibehält.
Wird zum Beispiel eine alphabetisch geordnete Liste von Studenten nach
deren Noten sortiert, so liefert ein stabiler Algorithmus eine Liste, in der
die Studenten mit gleichen Noten immer noch alphabetisch geordnet sind.
Eine nichtstabile Methode erzeugt eine Liste, in der diese ursprüngliche
Reihenfolge im allgemeinen nicht mehr gegeben ist.
Man unterscheidet:
- internes Sortieren: die zu sortierende Folge befindet sich im Hauptspeicher
(wahlfreier Zugriff);
- externes Sortieren: die zu sortierende Folge ist auf externe Speichermedien wie Bänder
oder Platten ausgelagert (i.a. sequentileller Zugriff).
|
 |

zwei ausfürliche Beispiele
|
 |

Bubblesort-Algorithmus
Sortieren durch direktes Austauschen
Quicksort-Algorithmus
Rekursive Sortierung (schnelle und allgemein einsetzbare Methode)
|