Sortieralgorithmen

Das Sortieren (und Suchen) ist in der Informatik umfas-send untersucht worden, weil Sortieralgorithmen in zahlreichen Anwendungen verwendet werden (Daten-banken, Compiler, Betriebssysteme etc.). Grundsätzlich gibt es drei Methoden zum Sortieren: Auswählen,Einfügen,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 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 so lange aus, bis alle Karten geordnet sind.

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

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

Beispiele:

1. Sortieren durch direktes Auswählen (Minimumsuche)
2. Sortieren durch Einfügen
3. Sortieren durch Austauschen (Bubblesort)
4. Sortieren durch Austauschen (Shakersort)
5. Sortieren durch Einfügen mit abnehmender Schrittweite (Shellsort)
6. Sortieren durch Rekursion (Quicksort)

Vergleich von (1) - (5)

Aufgabe:

Erweitere die hier vorgestellten Applets so, dass der Benutzer die Zahl der zu sortierenden Elemente festlegen kann. Die Werte werden als Zufallszahlen zwischen 0 und 99 initialisiert...