Sortieren


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.
  1. 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).

  2. 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)


Logo: Abteilungsseite, Pfeile: Seitenanfang, nächste Seite

Letzte Änderung 10. Februar 1998 ©