Die Musterlösung lässt die Auswahl zwischen den drei zu wählenden Verfahren und lässt auch die Freiheit, ob das Feld sortiert, unsortiert (d.h. absteigend sortiert) oder benutzerdefiniert ist.
MODULE Sortieren;
IMPORT Display;
CONST
untergrenze = 0;
obergrenze = 50 (*Hier können auch andere Werte gewählt werden!*);
TYPE
DatenFeld = ARRAY obergrenze + 1 OF INTEGER;
(* 1. Möglichkeit *)
PROCEDURE EinSort (VAR feld: DatenFeld; min, max: INTEGER);
VAR
trennung, frei: INTEGER;
s,hilfe: INTEGER;
BEGIN
s:=1;
FOR trennung := min + 1 TO max DO
s:=s+1;
(* Nimm eine Zahl und sortiere sie ggf. im linken Teil ein *)
hilfe := feld [trennung];
s:=s+1;
frei := trennung;
s:=s+1;
WHILE (frei > min) &
(feld [frei - 1] > hilfe) DO
(* Aufrücken! *)
s:=s+1;
feld [frei] := feld [frei -1];
s:=s+1;
frei := frei - 1;
s:=s+1;
END;
feld [frei] := hilfe; (* Die Zahl an der passenden Stelle einfügen*)
s:=s+1;
END;
END EinSort;
(* 2. Möglichkeit *)
PROCEDURE AuswahlSort (VAR feld: DatenFeld; min, max: INTEGER);
VAR
trennung, kleinstes, i: INTEGER;
hilfe,s: INTEGER;
BEGIN
s:=1;
FOR trennung := min TO max - 1 DO
s:=s+1;
kleinstes := trennung;
s:=s+1;
FOR i := trennung + 1 TO max DO (* kleinsten Wert im
nichtsort. Teil suchen *)
s:=s+1;
IF feld [i] < feld [kleinstes] THEN
s:=s+1;
kleinstes := i;
s:=s+1;
END;
END;
hilfe := feld [kleinstes];
s:=s+1;
FOR i := kleinstes TO trennung + 1 BY -1 DO
s:=s+1;
feld [i] := feld [i-1]; (*aufrücken *)
s:=s+1;
END;
feld [trennung] := hilfe;
s:=s+1;
END;
END AuswahlSort;
(* 3. Möglichkeit *)
PROCEDURE BubbleSort (VAR feld: DatenFeld; min, max: INTEGER);
VAR
pos: INTEGER;
hilfe,s: INTEGER;
vertauscht: BOOLEAN;
BEGIN
s:=0;
REPEAT (* bis ein Durchlauf ohne Vertauschungen stattfindet *)
vertauscht := FALSE;
s:=s+1;
FOR pos := min TO max -1 DO
s:=s+1;
IF feld [pos] > feld [pos + 1]
THEN s:=s+1;
hilfe := feld [pos]; (* vertausche zwei Werte *)
s:=s+1;
feld [pos] := feld [pos + 1];
s:=s+1;
feld [pos + 1] := hilfe;
s:=s+1;
vertauscht := TRUE;
s:=s+1;
END;
END;
UNTIL ~ vertauscht
END BubbleSort;
PROCEDURE FeldSortiert (VAR feld: DatenFeld); (*Erzeugt ein komplett sortiertes Feld*)
VAR i:INTEGER;
BEGIN
FOR i:=untergrenze TO obergrenze DO
feld [i]:=i;
Display. WriteInt (feld[i], 3);
END;
END FeldSortiert;
PROCEDURE FeldUnSortiert (VAR feld: DatenFeld); (*Erzeugt ein komplett unsortiertes (absteigend sortiertes) Feld*)
VAR i:INTEGER;
BEGIN
FOR i:=untergrenze TO obergrenze DO
feld [i]:=obergrenze-i;
Display. WriteInt (feld[i], 3);
END;
END FeldUnSortiert;
PROCEDURE FeldVonHand (VAR feld: DatenFeld); (*Erzeugt ein Feld von Hand*)
VAR i:INTEGER;
zahl:INTEGER;
ch:CHAR;
BEGIN
Display. WriteStr ("Bitte Zahlen eingeben! ");
FOR i:=untergrenze TO obergrenze DO
Display. WriteInt (i,3);
Display. WriteStr (":");
Display. ReadInt (zahl,3,ch);
feld [i]:=zahl;
Display. WriteStr (" ");
END;
END FeldVonHand;
PROCEDURE ProgMain*;
VAR
i: INTEGER;
daten: DatenFeld;
c: CHAR;
s:LONGINT;
BEGIN
Display. WriteStr ("Komplett sortiertes Feld (S), komplett unsortiertes Feld (U) oder Feld von Hand eingeben (H)?");
Display. ReadChar (c);
Display. WriteLn;
IF (c='S') OR (c='s') THEN
FeldSortiert (daten);
END;
IF (c='U') OR (c='u') THEN
FeldUnSortiert (daten);
END;
IF (c='H') OR (c='h') THEN
FeldVonHand (daten);
END;
Display. WriteLn;
Display. WriteStr ("Welchen Algorithmus? B: BubbleSort; E: EinSort A: AuswahlSort ");
Display. ReadChar (c);
Display. WriteLn;
IF (c='b') OR (c='B') THEN
BubbleSort (daten, untergrenze,
obergrenze); (* oder AuswahlSort/Bubblesort *)
END;
IF (c='e') OR (c='E') THEN
EinSort (daten, untergrenze,
obergrenze); (* oder AuswahlSort/Bubblesort *)
END;
IF (c='a') OR (c='A') THEN
AuswahlSort (daten, untergrenze,
obergrenze); (* oder AuswahlSort/Bubblesort *)
END;
Display.WriteStr ('Das sortierte Feld lautet: ');
Display.WriteLn;
FOR i := untergrenze TO obergrenze DO
Display.WriteInt (daten [i],3);
Display.WriteStr (' ');
END;
Display. WriteLn;
Display. WriteStr ("Dafür habe ich ");
Display. WriteInt (s, 5);
Display. WriteStr (" Schritte gebraucht");
Display.ReadChar (c);
END ProgMain;
END Sortieren.