Sortierverfahren

Aus ProgrammingWiki

Archivierte Version vom 2012-09-19T06:17:48+00:00. Aktuelle Version

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:

procedure minimum(n:integer);
var z:array[0..7] of integer;
var i,j,k,h:integer;
begin 
for i:=0 to 7 do 
begin  
z[i]:=random(20)+1; 
write(inttostr(z[i])+' ');  
end;
for i:=0 to 7 do  
begin  
 k:=i;  
 for j:=i to 7 do  
 if z[j]<z[k] then k:=j;  
 h:=z[i];  
 z[i]:=z[k];  
 z[k]:=h; 
end;
writeln('');
writeln('');
for i:=0 to 7 do write(inttostr(z[i])+' ');
end;

minimum(8);

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?

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