Sortierverfahren mit Struktogramm und einer Implementationsvariante unter Pascal

01.09.2008
von Mario Rasser

Kommentare geschlossen

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

Struktogramm zu Selection Sort

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] &lt; 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] &gt; 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

Insertion Sort 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]&gt;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

Merge Sort 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)

Tags: Delphi|Pascal|Sort|Sortierung
Abgelegt in: Tipps

Dieser Eintrag wurde am Montag, 01. September 2008 um 17:17 erstellt und ist abgelegt unter Tipps. Mit dem RSS 2.0 Feed kannst du den Antworten zu diesem Artikel folgen. Beides, Kommentare und Pings sind zurzeit geschlossen.

Kommentare sind geschlossen.