Sortierverfahren

Vorbemerkungen

Zunächst begeben wir uns mal vor die Tür :-)

Das Sortieren (und Suchen) ist in der Informatik umfassend untersucht worden, weil Sortieralgorithmen in zahlreichen Anwendungen verwendet werden
(Datenbanken, Compiler, Betriebssysteme etc.).

Grundsätzlich gibt es drei Methoden zum Sortieren:

• Auswählen

• Einfügen

• Austauschen

Wir besprechen diese Verfahren an Hand des Sortierens von Spielkarten: Beim Auswählen breitet man die Karten auf dem Tisch aus und wählt die niedrigste Karte. Anschließend wird die nächste Karte gewählt und hinter die niedrigste gereiht, usw. Beim Sortieren durch Einfügen hält man die Karten in der Hand, nimmt jeweils die nächste und fügt sie in einen am Tisch liegenden Stapel so ein, dass sie jeweils an der richtigen Stelle zu liegen kommt. Die Karten sind sortiert, sobald man keine Karte mehr in der Hand hält. Um die Karten durch Austauschen zu sortieren, breitet man die Karten in beliebiger Reihenfolge auf dem Tisch aus und tauscht dann die falsch liegenden Karten solange aus, bis der Satz geordnet ist.

Für die "Güte" eines Sortieralgorithmus sind folgende Kriterien ausschlaggebend:

  1.	Wie schnell sortiert der Algorithmus durchschnittlich Informationen? 
  2.	Wie schnell ist er im günstigsten und ungünstigsten Fall? 
  3.	Verhält sich der Algorithmus natürlich (d.h. hat er bei gut sortierten Listen 
        wenig und bei ziemlich ungeordneten Listen viel zu tun)? 
  4.	Ordnet er Elemente mit gleichen Schlüsseln um? 

Sortieralgorithmen bieten sich als grundlegendes Thema für die Analyse von Algorithmen an.

Literatur

• Fahldieck, Karl-Heinz: Algorithmen, Frankfurt am Main: Verlag Moritz Diesterweg, 1993
• Sedgewick, Robert: Algorithmen, Bonn:Addison-Wesley Publishing Company, 1992
• Hermann, Dietmar: Algorithmen Arbeitsbuch, Bonn; München; Paris, Addison-Wesley Publishing Company, 1992
• Junger, Hans u.a.: Informatik, Frankfurt am Main; Aarau, Verlag Moritz Diesterweg; Verlag Sauerländer AG, 1988