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.

Sortieren durch Auswählen (Minimumsuche)

Die Idee einer der einfachsten Sortieralgorithmen ist die folgende: Finde zunächst das kleinste Element im Datenfeld und tausche dieses gegen das an der ersten Stelle befindliche Element aus. Anschließend finde das zweitkleinste Element, tausche es gegen das zweite Element aus ... usw.

Diese Sortiermethode ist für kleine Dateien sehr gut brauchbar. Zu beachten ist, dass jedes Element tatsächlich nur einmal getauscht wird.

       Prinzip: Aus einer Menge wird das kleinste Elelment ausgewählt und mit dem ersten Element vertauscht.
       Diese Vorgänge werden wiederholt ,wobei die Anzahl der Elemente bei jeder Wiederholung von 
       vorn um eins verringert wird.
       Zuletzt werden nur noch zwei Elemente überprüft und gegebenenfalls vertauscht.

unsortiertes Feld 36 mit 99 vertauscht, anschließend kleinstes Element des Restfeldes (roter Pfeil) mit 99 vertauscht 77 mit 99 vertauscht, anschließend kleinstes Element des Restfeldes mit 99 vertauscht...

Implementiert könnte dies so aussehen:

Experimentieren Sie:
Ändern Sie den Bereich der Zufallszahlen
Verändern Sie die Größe des Feldes
Sortieren Sie eine beliebig große Menge - was muss alles verändert werden?

Sortieren durch Einfügen

       Prinzip: Man wählt ein Element (nacheinander vom zweiten bis zum letzten) und fügt es jeweils an die richtige 
       Stelle der davorstehenden geordneten Teilmenge ein. 

unsortiertes Feld; zweites Element herausgenommen und vor dem Ersten eingefügt sechstes Element genommen und als viertes eingefügt, dabei werden viertes und fünftes (alt) neues fünftes und sechstes Element Letztes Element an die richtige Stelle, Feld vollständig sortiert

Implementieren Sie das Sortieren durch Einfügen analog zum Sortieren durch Auswählen!

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