procedure Tauschen (var E1, E2 : TElement);
(* ------------------------------------ *)
var
hilf : TElement;
begin
hilf:= E1;
E1 := E2;
E2 := hilf
end;
procedure TWortListe.Bubblesort1;
(* -------------------------------------------------------------------- *)
(* Auftrag: lineares Sortieren durch systematisches Vergleichen aller *)
(* Elemente und Tauschen mit dem nachfolgenden Element *)
(* Vorher : Liste ist initialisiert *)
(* Nachher: Liste ist aufsteigend sortiert *)
(* -------------------------------------------------------------------- *)
var
Durchlauf,
i : integer;
begin
for Durchlauf := 1 to (Listenlaenge - 1) do
begin
for i := 1 to (Listenlaenge - 1) do
begin
if Kollektion[i] > Kollektion[i+1]
then Tauschen(Kollektion[i], Kollektion[i+1]);
end;
end; (* for Durchlauf *)
end;
procedure TWortListe.Bubblesort2;
(* ------------------------------------------------------------------- *)
(* Auftrag: lineares Sortieren durch Vertauschen des nachfolgenden *)
(* Elements im Restfeld, das von hinten verkleinert wird. *)
(* Vorher : Liste ist initialisiert *)
(* Nachher: Liste ist aufsteigend sortiert *)
(* -------------------------------------------------------------------- *)
var
Durchlauf,
i,
Endmarke : integer;
begin
Endmarke := ListenLaenge - 1;
for Durchlauf := 1 to (ListenLaenge - 1) do
begin
for i := 1 to (Endmarke) do
begin
if Kollektion[i] > Kollektion[i+1]
then
begin
Tauschen(Kollektion[i], Kollektion[i+1]);
end;
end;
Endmarke := Endmarke - 1;
end;
end;
procedure TWortListe.Bubblesort3;
(* ------------------------------------------------------------------ *)
(* Auftrag: lineares Sortieren durch Vergleichen und Vertauschen des *)
(* nachfolgenden Elements bis nicht mehr getauscht wird. *)
(* Endmarke rueckt vor und verkleinert Restfeld *)
(* vorher : Kollektion ist initialisiert *)
(* nachher: Kollektion ist aufsteigend sortiert *)
(* ------------------------------------------------------------------ *)
var
y,
Endmarke : integer;
IstSortiert : boolean;
begin
Endmarke := Listenlaenge - 1 ;
IstSortiert := false;
while NOT IstSortiert do
begin
IstSortiert := true ;
for y := 1 to endmarke do
begin
if Kollektion[y] > Kollektion[y+1]
then
begin
IstSortiert := false;
Tauschen (Kollektion[y], Kollektion[y+1]);
end;
end;
Endmarke := Endmarke - 1; (* Restfeld verkleinern *)
end;
end;
procedure TListe.shakersort1;
(* ------------------------------------------------------------------- *)
(* Aufgabe: *)
(* lineares Sortieren durch Vergleichen und Vertauschen des *)
(* nachfolgenden Elements. *)
(* Das Feld wird abwechselnd von links nach rechts durchlaufen, *)
(* dabei die Feldgrenzen nach innen verkleinert solange die linke *)
(* Grenze kleiner ist als die rechte. *)
(* vorher : Kollektion ist initialisiert *)
(* nachher: Kollektion ist aufsteigend sortiert *)
(* ------------------------------------------------------------------- *)
var
y,
linkeGrenze,
rechteGrenze,
tauschPos : integer;
begin
linkeGrenze := 1;
rechteGrenze := ListenLaenge - 1;
tauschPos := linkeGrenze;
while linkeGrenze < rechteGrenze do
begin
for y := linkeGrenze to rechteGrenze do
begin
if Kollektion[y] > Kollektion[y+1]
then
begin
Tauschen(Kollektion[y], Kollektion[y+1]);
tauschPos := y;
end;
end; (* for y *)
rechteGrenze := tauschPos - 1;
for y := rechteGrenze downto linkeGrenze do
begin
if Kollektion[y] > Kollektion[y+1]
then
begin
Tauschen(Kollektion[y], Kollektion[y+1]);
tauschPos := y;
end;
end; (* for y *)
linkeGrenze := tauschPos +1;
end; (* while *)
end;
procedure TListe.auswahlsort;
(* ------------------------------------------------------------------- *)
(* Aufgabe: lineares Sortieren durch direkte Auswahl und Vertauschen *)
(* der Position. *)
(* vorher : Kollektion ist initialisiert *)
(* nachher: Kollektion ist aufsteigend sortiert *)
(* ------------------------------------------------------------------- *)
var
i,
y,
indexmin : integer; (* Index des kleinsten Elem. *)
begin
for i := 1 to (ListenLaenge - 1) do
begin
indexmin := i;
for y := (i + 1) to ListenLaenge do
begin (* im Restfeld das kleinste *)
if Kollektion[y] < Kollektion[indexmin] (* Element suchen *)
then indexmin := y;
end; (* for y *)
Tauschen(Kollektion[i], Kollektion[indexmin]); (* Positionen tauschen *)
end; (* for i *)
end;
procedure TWortListe.Quicksort(anfang, ende: Word);
(* ------------------------------------------------------------------- *)
(* Auftrag: Feld teilen und nach mittlerem Vergleichselement grob *)
(* vorsortieren. Linke und rechte Haelfte rekursiv bearbeiten *)
(* Vorher : Kollektion ist initialisiert *)
(* nachher: Kollektion ist aufsteigend sortiert *)
(* ------------------------------------------------------------------- *)
var LinkerZeiger,
RechterZeiger : word;
VergleichsElement : string;
begin
LinkerZeiger := anfang;
RechterZeiger := ende;
VergleichsElement := Kollektion[(LinkerZeiger + RechterZeiger) div 2];
repeat
while (Kollektion[LinkerZeiger] < VergleichsElement) do //auf der linken
begin // Seite einen
LinkerZeiger := LinkerZeiger + 1; // 'Falschen' suchen
end;
while (Kollektion[RechterZeiger] > VergleichsElement) do //auf der rechten
begin //Seite einen
RechterZeiger := RechterZeiger-1; // 'Falschen' suchen
end;
if LinkerZeiger <= RechterZeiger // haben sich noch nicht ueberkreuzt
then // dann tauschen und eins weiter
begin
Tauschen (Kollektion[LinkerZeiger], Kollektion[RechterZeiger]);
LinkerZeiger := LinkerZeiger + 1;
RechterZeiger := RechterZeiger - 1;
end; (* if *)
until RechterZeiger < LinkerZeiger; // Grobsortierung beendet
if anfang < RechterZeiger // mehr als 1 El. vorhanden
then quicksort(anfang, RechterZeiger);
if LinkerZeiger < ende
then quicksort(LinkerZeiger, ende);
end;
|
