Musterlösung zu Sortieralgorithmen

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.

Zurück zur den Sortieralgorithmen