Exkurs: "Tabbed Notebook"

Die zuletzt besprochenen Kodierverfahren könnten anstelle mit Hilfe von Menüeinträgen auf sogenannten Registerkarten (Karteikarten, tabbed Notebooks) dargestellt werden. Dies ermöglicht eine sehr übersichtliche Handhabung von Programmteilen (vgl. Standard-Software). Der Anwender wählt eine Seite aus, indem das Register der gewünschten Seite in der obersten Zeile des Dialogelements angelickt wird.

Die dazu notwendige Komponente wird (beispielsweise) aus der Palette "WIN3.11" ausgewählt und am Formular platziert. Die Seiten, die in dem Register-Arbeitsblattfenster erscheinen, entsprechen den Strings, die als Wert der Eigenschaft Pages angegeben werden. Auf eine bestimmte Seite auf dem Arbeitsblatt kann schließlich mit der Eigenschaft ActivePagezugegriffen werden. Die Eigenschaft TabsPerRow legt fest, wie viele Register in einer Zeile erscheinen sollen....

procedure Tform1.FormCreate(Sender...)
begin
Notebook1.ActivePage:='Verschiebechiffre';
...
end;

Auf den einzelnen Registerseiten können Objektelemente wie gewohnt platziert werden.

14 Sortieren

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ählenbreitet man gleichsam 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ünstigstenFall?
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?

14.1 Sortieren durch direktes Auswählen

Die Idee einer der einfachsten Sortieralgorithmen ist die folgende: Finde zunächst das kleinste Element im Datenarray 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.

procedure Tform1.Minimumsuche(Sender:TObject);
var h:array[1..100] of byte;
i,j,min,hilfsvar:byte;
begin 
 ...
 for i:=1 to 99 do begin
min:=i;
For j:=i+1 to 100 do
if h[j]<min then min:=j;
hilfsvar:=h[min];
h[min]:=h[i];
h[i]:=hilfsvar;
end;
end; 

Diese Sortiermethode ist für kleine Dateien sehr gut brauchbar. Zu beachten ist, dass jedes Element tatsächlich nur einmal getauscht wird.

14.2 Sortieren durch Einfügen

procedure Tform1.Einfuegen (Sender:TObject);

var h:array[1..100] of byte;
i,j,x:byte;
begin
 ...
 for i:=2 to 100 do begin
x:=h[i];
j:=i-1;
while (x<h[j]) and (j>0) do begin
h[j+1]:=h[j];
dec(j);
end;
h[j+1]:=x;
end;
end;

14.3 Bubblesort (Sortieren durch Austauschen)

Procedure Tform1.BubbleSort(Sender: Tobject);
var h:array[1..100] of byte;
i,j,hilfsvar:byte;
begin
 ...
for i:=2 to 100 do begin
for j:=100 downto i do begin
if h[j-1]>h[j] then begin
hilfsvar:=h[j-1];
h[j-1]:=h[j];
h[j]:=hilfsvar;
end;
end;
end;
end;

Der Algorithmus erhält seinen Namen von der Tatsache, dass die Elemente - ähnlich wie Blasen im einem Glas Mineralwasser - aufsteigen, bis sie an der richtigen Stelle sind.

14.4 ShakerSort (Sortieren durch Austauschen)

procedure TForm1.ShakerSort(Sender:TObject);
var h:array[1..100] of byte;
j,k,l,r:byte;
begin
...
l:=2;
r:=100;
k:=100;
repeat
for j:=r downto l do begin
if h[j-1]>h[j] then begin
tauschen(h[j-1],h[j]);
k:=j;
end;
end;
l:=k+1;
for j:=l to r do begin
if h[j-1]>h[j] then begin
tauschen(h[j-1],h[j]);
k:=j;
end;
 end;
 r:=k-1;
until l>r;
end; 

Das Sortieren durch Austauschen ist jedenfalls schlechter als das Sortieren durch Einfügen und schlechter als das Sortieren durch Auswählen.

14.5 ShellSort (Sortieren durch Einfügen mit abnehmender Schrittweite)

procedure Tform1.ShellSort(Sender:TObject);
var h:array[1..100] of byte;
I,j,k,hilfe:byte;
begin
...
k:=1;
repeat 
k:=3*k+1
until k>100;
repeat
k:=k div 3;
for i:=k+1 to 100 do begin
hilfe:=h[i];
j:=i;
while (h[j-k]>hilfe) and (j>k) do begin
h[j]:=h[j-k];
dec(j,k);
end;
h[j]:=hilfe;
end;
until k=1;
...
end;

Durch das anfängliche Sortieren von Elementen, die weiter voneinander entfernt sind, werden Elemente, die weit von ihrem Platz in der sortierten Menge liegen, rascher über größere Strecken bewegt. Dadurch erhält der ShellSort eine bedeutsame Effizienz für stark ungeordnete Mengen...

14.6 QuickSort

Das Grundprinzip des Sortierverfahrens ist "teile und herrsche". Eine Datei (oder ein Array) wird einfach in zwei Teile zerlegt und schließlich in ihrern beiden Teilen sortiert. Dies wird rekursiv implementiert: Die allgemeine Prozedur wählt einen Vergleichswert und zerlegt dann das Feld in zwei Teile mit allen Elementen größer oder gleich dem Vergleichswert auf einer Seite und alle kleiner als der Vergleichswert auf der anderen Seite. Dieser Vorgang wird für beide entstandenen Teil wiederholt bis die Datei sortiert ist.

type feld=array[1..100] of byte;
procedure Tform1.QuickSort(Sender:TObject);
var h:feld;
begin
...
sortiere(1,100,h);
...
end;   
Die Prozedur sortiere(l,r,h)stellt den eigentlichen Algorithmus dar:
procedure Tform1.sortiere(l,r:integer; varh:feld);
var i,j,k:byte;
eintrag:byte;
begin
 i:=l;
j:=r;
eintrag:=h[(l+r) div 2];
repeat
while h[i]<eintrag do inc(i);
while eintrag<h[j] do dec(j);
if i<=j then begin
tauschen(h[i],h[j]);
inc(i);
dec(j);
end;
until i>j;
if l<j then sortiere(l,j,h);
if r>i then sortiere(i,r,h);
end;