Sortierverfahren mit Struktogramm und einer Implementationsvariante unter Pascal
01.09.2008
von Mario Rasser
von Mario Rasser
Diese unten aufgeführten Struktogramme und Algorithmen, erheben kein Anspruch auf Fehlerlosigkeit. Sie wurden aber nach besten Wissen und Gewissen erarbeitet und auch erfolgreich unter Borland Turbo Pascal 6.0/7.0 getestet.
1. Selektion-Sort
weitere Bezeichnungen
- Selection-Sort
- Sortieren durch (direktes) Auswählen
Prinzip
- man sucht den kleinsten Wert
- diesen tauscht man mit dem ersten Element
- man sucht den nächsten kleinsten Wert und setzt ihn an die zweite Stelle
- dies macht man solange bis das komplette Feld (Array) sortiert ist
- Es ist eines der einfachsten, aber auch langsamsten Sortierverfahren
Struktogramm
Quellcode
{Beispielwerte}
CONST min=0;
max=1000;
{Ende Bespielwerte}
TYPE TFeld=Array[min..max] of Real; {}
Procedure Selection_Sort(var feld : TFeld; min, max : integer);
var i,j : integer;
a : real; {}
Begin
For i:=min to max-1 do
Begin
a:=feld[i];
For j:=i+1 to max do
Begin
if feld[j] < a then
Begin
a:=feld[j];
feld[j]:=feld[i];
feld[i]:=a;
end;
end;
end;
end;
Insertion-Sort
weitere Bezeichnungen
- Sortieren durch (direketes) Einfügen
Prinzip
- man betrachtet ein Element nach dem anderen und sucht die richtige Stelle und fügt dieses Element ein
- das Einfügen wird realisiert indem die größeren Elemente eins nach hinten verschoben werden und das Element an dieser nun freien Stelle eingefügt wird
Variante 1
Quellcode
Beispielwerte}
CONST min=0;
max=1000;
{Ende Bespielwerte}
TYPE TFeld=Array[min..max] of Real; {}
Procedure Insertion_Sort(var feld : TFeld; min, max : Integer);
VAR Hilfe : Real; {}
i,j,k : Integer;
Begin
For i:=min to max-1 do
Begin
For j:=i+1 to max do
Begin
if feld[i] > feld[j] then
Begin
hilfe:=feld[j];
For k:=j-1 downto i do
Begin
feld[k+1]:=feld[k];
end;
feld[i]:=hilfe;
end;
end;
End;
End;
Variante 2
Struktogramm
Quellcode
{Beispielwerte}
CONST min=0;
max=1000;
{Ende Bespielwerte}
TYPE TFeld=Array[min..max] of Real; {}
procedure Insertion_Sort_2(var Feld : TFeld; min, max : Integer);
var i,j : Integer;
hilfe : Real; {}
Begin
For i:=min+1 to max do
Begin
hilfe:=Feld[i];
j:=i;
While Feld[j-1]>hilfe do
Begin
Feld[j]:=Feld[j-1];
j:=j-1;
End;
Feld[j]:=hilfe;
End;
end;
Merge-Sort
weitere Bezeichnungen
- Misch-Sort
- Mischsortierung
Prinzip
- man erstellt zwei sortierte Teilmengen (von min bis mitte und von mitte+1 bis max)
- dieses zwei Teilmengen werden dann gemischt, somit entsteht ein komplett sortiertes Feld
- dieses Verfahren ist programmiertechnisch etwas komplexer als die oben genannten trivialen Sortier-Modelle. Es ist aber wesentlich schneller
- Der Zeitaufwand für N Elemente steigt mit N*log(N)
- Verwirklichung der Sortierung durch Rekursion (die zwei Teilmengen werden durch die Rekursion wieder in Teilmengen zerlegt, dies geschieht solange bis nur noch zwei Elemente verglichen werden, danach “läuft” die Rekursion wieder rückwärts)
Struktogramm
Quellcode
{Beispielwerte}
CONST min=0;
max=1000;
{Ende Bespielwerte}
TYPE TFeld=Array[min..max] of Real; {}
procedure Mischen(var feld : TFeld; unten, mitte, oben : integer);
var dummy : TFeld;
j,i,k,s,ir,l : Integer;
Begin
j:=mitte+1;
i:=unten;
k:=unten;
While (i<=mitte) and (j<=oben) do
Begin
if (feld[i] <= feld[j]) then
Begin
dummy[k]:=feld[i];
i:=i+1;
end
else
Begin
dummy[k]:=feld[j];
j:=j+1;
end;
k:=k+1
end;
if i>mitte then
For s:=j to oben do
dummy[k+s-j]:=feld[s]
else
For ir:=i to mitte do
dummy[k+ir-i]:=feld[ir];
For l:=unten to oben do feld[l]:=dummy[l];
end;
procedure Misch_Sort(var feld:TFeld;unten,oben:integer);
var Mitte : Integer;
Begin
if unten < oben then
Begin
Mitte:=(unten+oben) div 2;
Misch_Sort(feld,unten,mitte);
Misch_Sort(feld,(mitte+1),oben);
Mischen(feld,unten,mitte,oben);
end;
end;
(Archiviert aus unseren alten Tipps und Tricks Sektion)