PMG/Kurs 11/Sortierverfahren

Wiki-Quelltext dieser Seite.

<language>Pascal</language>
== Vorbemerkungen ==


 <font size=4 color=red><b>Zunächst begeben wir uns mal vor die Tür :-)</b></font>

Das Sortieren (und Suchen) ist in der Informatik umfassend untersucht worden, weil Sortieralgorithmen in zahlreichen Anwendungen verwendet werden <br>(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.