Qualifikationsphase 1
Das Sortierproblem
SelectSort
Der Name "Selectsort" kommt von selection (dt. Auswahl), da in jedem Schritt das größte (oder kleinste) Element selektiert wird. Ein Feld wird einmal vollständig durchlaufen. Dabei wird durch einfache Vergleiche das größte Element herausgesucht (selektiert) und zum Schluss an das Feldende gepackt. Dieser Schritt wird nun mit dem kleineren Teilfeld (Feld ohne das letzte Element) wiederholt und wiederholt usw. Irgendwann sind alle Elemente sortiert. Aufgrund der Auswahl von Elementen wird dieses Verfahren auch als "Sortierung durch Auswahl" bezeichnet.
55 7
78 12
42 max=78
78-->42
55 7
42 12
78
max=55 55-->12
12 7
42
55 78
max=42 42-->42
12 7
42 55
78 max=12
12-->7
7 12
42 55 78
procedure selectionsort(anzahl:integer);
var i, j: integer;
max:???;
begin
for i:=anzahl downto 2 do
q:=1;
max:=feld[q];
for j:=2 to i do
if feld[j] > feld[q] then
begin
max:=feld[j];
q:=j;
end;
tausche(feld[q],zahl[i]);
end;
end;
Die Prozedur ist mit Hilfe eines Arrays formuliert. Um einfach
verkettete Listen zu sortieren, muss das Programm etwas angepasst
werden. Die Prozedur könnte dann wie folgt aussehen:
procedure TMain.BtVokSortClick(Sender: TObject);
var i, j, q: integer;
max:string;
tausch,tauschi:TVokabel;
begin
for I := zaehler downto 2 do
begin
liste.toFirst;
max:=(liste.getObject as TVokabel).vokabel;
tausch:=TVokabel.Create;
tausch.vokabel:=TVokabel(liste.getobject).vokabel;
tausch.deutsch:=TVokabel(liste.getobject).deutsch;
q:=1;
for j := 2 to i do
begin
liste.next;
if TVokabel(Liste.getobject).Vokabel > max
then
begin
max := (liste.getobject
as TVokabel).vokabel;
tausch.vokabel:=(liste.getobject as TVokabel).vokabel;
tausch.deutsch:=(liste.getobject as TVokabel).deutsch;
q:=k;
end;
end;
tauschi:=TVokabel.Create;
tauschi.vokabel:=(liste.getobject as TVokabel).vokabel;
tauschi.deutsch:=(liste.getobject as TVokabel).deutsch;
liste.setobject(tausch);
liste.toFirst;
for k := 1 to stelle-1 do liste.next;
liste.setobject(tauschi);
end;
end;
BubbleSort
Ein Feld wird einmal vollständig durchlaufen. Dabei werden die jeweiligen Nachbarelemente miteinander verglichen und ggf. ausgetauscht. Am Ende befindet sich das größte Element am Ende des Feldes. Dieser Schritt wird nun mit dem kleineren Teilfeld (Feld ohne das letzte Element) wiederholt.
55 7
78 12 42
55<7 tauschen
7 55
78 12 42
55<78
7 55
78 12
42 78<12 tauschen
7 55 12
78 42
78<42 tauschen
7 55
12 42
78
7<55
7 55
12 42
78
55<12 tauschen
7 12
55 42
78
55<43 tauschen
7 12
42 55
78 7<12
7 12
42 55
78 12<42
7 12
42 55
78 7<12
7 12
42 55 78
procedure bubblesort(var f: Array of ????,anzahl:integer);
var i,j: Integer;
temp:???;
begin
for i:=anzahl downto 2 do
for j:=2 to i do
if f[j-1] > f[j] then begin
temp := f[j-1];
f[j-1] := f[j];
f[j] := temp;
end;
end;
InsertSort
Ein kleineres bereits sortiertes Teilfeld wird um ein Element erweitert. Dieses neu hinzugekommene Element wird durch Vergleiche und Verschiebungs- oder Vertauschungsoperationen an die "richtige" Stelle dieses größeren Teilfeldes eingefügt. Dieser Schritt wird wiederholt, bis das Teilfeld maximal ist (also dem Gesamtfeld entspricht). Dann sind wir fertig und die Elemente sind sortiert.
Bei einem Kartenspiel bekommt man nacheinander eine bestimmte Anzahl von Karten ausgehändigt. Erst hat man eine in der Hand, dann werden es zwei, drei, vier, ... Damit man da den Überblick behält sorgt man am besten dafür, daß die Karten sortiert in der Hand liegen. Kommt eine neue Karte hinzu, wird diese direkt an die richtige Position gesteckt.
Aufgrund des Einfügens von Elementen in eine sortierte Menge wird dieses Verfahren auch als "Sortierung durch Einfügen" bezeichnet.
55
7 78
12 42
55 sortiert
7 55
78 12
42 7, 55 sortiert
7 55
78 12
42 7,55,78 sortiert
7 12
55 78
42
7,12,55,78 sortiert
7 12
42 55 78
7,12,42,55,78 sortiert
Die benötigten Prozeduren lassen sich im Interner finden.