(* This program initializes an array and performs
  various different sorts. *)

MODULE Sort;
FROM InOut IMPORT Write,WriteLn,WriteCard,WriteInt,Read,WriteString;


CONST n= 256;
     nn=512;

TYPE index =[0..nn];
    item = RECORD
             key : INTEGER;
           END;
VAR i : index;
   r : INTEGER;
   a : ARRAY [-15..nn] OF item;
   z : ARRAY [1..n] OF INTEGER;
   Ch: CHAR;

PROCEDURE BubbleSort;
VAR i,j : index;
   x : item;

BEGIN
 FOR i := 2 TO n DO
   FOR j := n TO i BY -1 DO
     IF a[j-1].key > a[j].key THEN
       x := a[j-1];
       a[j-1] := a[j];
       a[j] := x;
     END
   END
 END
END BubbleSort;

PROCEDURE Bubblex;
VAR j,k,l : index;
   x : item;

BEGIN
 l := 2;
 REPEAT
   k := n;
   FOR j := n TO l BY -1 DO
     IF a[j-1].key > a[j].key THEN
       x := a[j-1]; a[j-1] := a[j]; a[j] := x;
       k := j
     END
   END;
 l := k + 1;
 UNTIL l > n
END Bubblex;

PROCEDURE ShakerSort;
VAR j,k,l,r : index;
   x : item;

BEGIN
 l := 2; r := n; k := n;
 REPEAT
   FOR j := n TO l BY -1 DO
     IF a[j-1].key > a[j].key THEN
       x := a[j-1];
       a[j-1] := a[j];
       a[j] := x;
       k :=j
     END
   END;
   l := k + 1;
   FOR j := l TO r DO
     IF a[j-1].key > a[j].key THEN
       x := a[j-1];
       a[j-1] := a[j];
       a[j] := x;
       k :=j
     END
   END;
   r := k - 1;
 UNTIL l > r
END ShakerSort;

PROCEDURE QuickSort;

 PROCEDURE sort(l,r:index);
 VAR i,j : index;
     x,w : item;
 BEGIN
   i := l; j :=r;
   x := a[(l + r) DIV 2];
   REPEAT
     WHILE a[i].key < x.key DO INC(i) END;
     WHILE x.key < a[j].key DO DEC(j) END;
     IF i <= j THEN
       w := a[i];
       a[i] := a[j];
       a[j] := w;
       INC(i);
       DEC(j);
     END;
   UNTIL i > j;
   IF l < j THEN sort(l,j) END;
   IF i < r THEN sort(i,r) END;
 END sort;
BEGIN
 sort(1,n)
END QuickSort;

PROCEDURE QuickSort1;
CONST m = 12;
TYPE  ss = [0..m];
VAR i,j,l,r : index;
   x,w : item;
   s : ss;
   stack : ARRAY [1..m] OF RECORD l,r : index END;
BEGIN
 s := 1; stack[1].l := 1; stack[1].r := n;
 REPEAT
   l := stack[s].l; r := stack[s].r; DEC(s);
   REPEAT
     i := l; j := r; x := a[(l + r) DIV 2];
     REPEAT
       WHILE a[i].key < x.key DO INC(i) END;
       WHILE x.key < a[j].key DO DEC(j) END;
       IF i <= j THEN
         w := a[i]; a[i] := a[j]; a[j] := w;
         INC(i);DEC(j);
       END;
     UNTIL i > j;
     IF i < r THEN
       INC(s); stack[s].l := i; stack[s].r := r;
     END;
     r := j
   UNTIL l >=r
 UNTIL s = 0
END QuickSort1;

BEGIN (*Main*)
 i := 0;
 r :=54;
 REPEAT
   INC(i);
   r := (8 * r) MOD 2141;
   z[i] :=r;
 UNTIL i = n;
 FOR i := 1 TO n DO
   a[i].key := z[i];
 END;
 BubbleSort;
 FOR i := 1 TO n DO
   WriteString("Changed BubbleSort-> ");
   WriteInt(a[i].key,3);
   WriteLn;
 END;
 WriteLn;
 Read(Ch);
 FOR i := 1 TO n DO
   a[i].key := z[i];
 END;
 QuickSort;
 FOR i := 1 TO n DO
   WriteString("Changed QuickSort-> ");
   WriteInt(a[i].key,3);
   WriteLn;
 END;
 WriteLn;
 Read(Ch);
 FOR i := 1 TO n DO
   a[i].key := z[i];
 END;
 QuickSort1;
 FOR i := 1 TO n DO
   WriteString("Changed QuickSort1-> ");
   WriteInt(a[i].key,3);
   WriteLn;
 END;
 WriteLn;
 Read(Ch);
 FOR i := 1 TO n DO
   a[i].key := z[i];
 END;
 Bubblex;
 FOR i := 1 TO n DO
   WriteString("Changed Bubblex-> ");
   WriteInt(a[i].key,3);
   WriteLn;
 END;
 WriteLn;
 Read(Ch);
 FOR i := 1 TO n DO
   a[i].key := z[i];
 END;
 ShakerSort;
 FOR i := 1 TO n DO
   WriteString("Changed ShakerSort-> ");
   WriteInt(a[i].key,3);
   WriteLn;
 END;
 WriteLn;
END Sort.