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)