Sortierverfahren

Das Sortieren (und Suchen) ist in der Informatik umfassend untersucht worden. Sortieralgorithmen werden in zahlreichen Anwendungen verwendet - etwa in Datenbanken, Compilern, Betriebssystemfunktionen, etc.). Grundsätzlich gibt es drei Methoden zum Sortieren:

• Sortieren durch Auswählen
• Sortieren durch Einfügen
• Sortieren durch Austauschen

Wir besprechen diese Verfahren zunächst an Hand des Sortierens von Spielkarten. Beim Auswählen breitet man gleichsam die Karten auf dem Tisch aus und wählt die niedrigste Karte. Anschließend wird die nächst höhere Karte gewählt und hinter die niedrigste gereiht, usf. 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 liefen 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 so lange (paarweise) aus, bis alle Karten geordnet sind.

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?

Alle hier behandelten Sortierverfahren werden als einfache Java-Applikationen realisiert. Die Daten werden jeweils durch Zufallszahlen erzeugt. Sollen die Algorithmen auf einer WebSeite dargestellt werden, ist die Verwendung von Applets unabdingbar.