(* ********* Zonnon online collection ***********
 * Sorting: Shaker Sort (Chapter 2, Example 2.5)
 *
 * This example is a part of Prof. Nikalus Wirth's book
 * www.zonnon.ethz.ch/usergroup
 * (c) ETH Zurich 
 *)

module Main;
    const MAX_SIZE = 20;
  
    type ElementOfArray = integer;
    type DefaultArray = array MAX_SIZE of ElementOfArray;
    var MyArray: DefaultArray;

    (***** Implementation *****)
    
    procedure ShakerSort(var a: DefaultArray; n: integer);
    var j,k,L,R: integer; x: ElementOfArray;
    begin
       L := 1; R := n - 1; k := n - 1;
       repeat
          for j := R to L by -1 do 
             if  a[j-1] > a[j] 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 by +1 do
             if  a[j-1] > a[j] 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;

    (***** Example support *****)

    procedure FillTheArray;
    var i:integer;
    begin
      for i := 0 to MAX_SIZE - 1 do 
        MyArray[i] := abs( 10 - i ); 
      end; 
    end FillTheArray;
 
    procedure PrintTheArray;
    var i:integer;
    begin
       writeln("Array:");
       for i := 0 to MAX_SIZE - 1 do
          write( MyArray[i]:2, ', ' ); 
       end; 
       writeln;
    end PrintTheArray;
    
    procedure Execute;
    begin
       ShakerSort(MyArray, MAX_SIZE); 
    end Execute;
begin
 writeln("Example 2.5 (Shaker sort)");
 FillTheArray;
 PrintTheArray;
 Execute;
 PrintTheArray;
 write("Press Enter to continue"); readln
end Main.