PROGRAM TestSearches (Input,Output);

CONST
   MaxSize = 5000;

   m = 100000000;   {random num generator}     
   b = 31415821;
   m1 = 10000;

TYPE
   ArrayType = Array[1..MaxSize] of Integer;
   
VAR
   TestArray : ArrayType;
   NumTests, Size, MaxKey, SearchType, binCount : Integer;
   RandNum : Integer4;
   Another : Char;
   Again : Boolean;






{Generate a pseudo-random number between 0 and 1.
RandNum should be seeded at start of each program. }

FUNCTION Random : Real;


FUNCTION Mult (p, q :Integer4) : Integer4;
Var 
   p1 , p0, q1, q0 : Integer4;
Begin
   p1 := p DIV m1;
   p0 := p MOD m1;
   q1 := q DIV m1;
   q0 := q MOD m1;
   Mult := (((p0*q1 + p1*q0) MOD m1) * m1 + p0*q0) MOD m;
End;


Begin
   RandNum := (Mult(RandNum,b) + 1) MOD m;
   Random := RandNum / m;
End;



{  Test randomness of random number generator
FUNCTION Chisquare (N : Integer) : Real;
Const
   Rmax = 100;
Var
   i, j, t : Integer;
   f : Array[0..Rmax] of Integer;
   A : ArrayType; 
Begin
   Writeln('Seed');
   Readln(RandNum);
   FOR i := 0 to Rmax DO
      f[i] := 0;

   FOR i := 1 to N DO
    Begin
     t := Trunc (Random * Rmax);
     f[t] := f[t] + 1;
     A[i] := t;
    End;

   i := 1;
   REPEAT
      FOR j := 0 to 4 DO
         Write(A[i+j]);
      Writeln;
      i := i + 5;
   UNTIL i >= N;

   t := 0;
   FOR i := 0 to Rmax-1 DO
      t := t + f[i]*f[i];
   Chisquare := (Rmax*t / N) - N;
End;   
}




PROCEDURE QuickSort (Var A : ArrayType;
                     left, right : Integer);
Var
   p, i, j, temp : Integer;
Begin
   IF left < right THEN
    Begin
     p := left;
     i := left + 1;
     j := right;
     REPEAT
       WHILE (A[i] <= A[p]) AND (i <= j) DO
          i := i + 1;
       WHILE (A[j] > A[p]) AND (i <= j) DO
          j := j - 1;
       IF i < j THEN
        Begin
         temp := A[i];
         A[i] := A[j];
         A[j] := temp;
         i := i + 1;
         j := j - 1;
        End;
     UNTIL j < i;
     temp := A[j];
     A[j] := A[p];
     A[p] := temp;
     p := j;
     QuickSort(A,left,p-1);
     QuickSort(A,p+1,right);
    End;

End;







FUNCTION SequentialSearch (Var R : ArrayType;
                           KeyZero : Integer;
                           Size : Integer) 
           : Integer;
Var
   j : Integer;
 
Begin
   j := 1;
   WHILE (R[j] <> KeyZero) AND (j <= Size) DO
      j := j + 1;
   IF j = Size THEN
      IF R[j] = KeyZero THEN
         SequentialSearch := j
      ELSE    
         SequentialSearch := Size + 1
   ELSE
     SequentialSearch := j;
End;




PROCEDURE BinarySearch (Var A : ArrayType;
                       KeyZero : Integer;
                       left, right : Integer;
                       Index : Integer);
Var 
   mid : Integer;
Begin
   IF left > right THEN
     Index := 0
   ELSE
     Begin
      binCount := binCount + 1;
      mid := (left + right) DIV 2;
      IF KeyZero = A[mid] THEN
         Index := mid
      ELSE
         IF KeyZero < A[mid] THEN
            BinarySearch(A,KeyZero,left,mid-1,Index)
         ELSE
            BinarySearch(A,KeyZero,mid+1,right,Index);
     End;  
End;


PROCEDURE BinaryItSearch (Var A : ArrayType;
                       KeyZero : Integer;
                       Size : Integer;
                       Index : Integer; 
                       Var Count : Integer);
Var 
   mid, left, right : Integer;
Begin
  left := 1; 
  right := Size;
  Repeat
     Count := Count + 1;
     mid := (left + right) DIV 2;
     IF KeyZero < A[mid] THEN
        right := mid - 1
     ELSE
        left := mid + 1;
  Until (KeyZero = A[mid]) OR (left > right);
 
  IF KeyZero = A[mid] THEN
     Index := mid
  ELSE
     Index := 0;
End;





PROCEDURE FillArray (VAR TestArray : ArrayType;
                     Size, MaxKey : Integer);
Var
   i, j : Integer;
 
Begin
   FOR i := 1 to Size DO
    Begin
      TestArray[i] := Trunc(Random * MaxKey);
     { Writeln(TestArray[i]);}
    End;

{   i := 1;
   REPEAT
       FOR j := 0 TO 4 DO
         Write(TestArray[i+j]);
       Writeln;
       i := i + 5;
    UNTIL i >= Size; }
End;





PROCEDURE Test (Size, MaxKey, NumSearches,
                SearchType : Integer);
Var 
   i, j, k : Integer;
   SearchKey, Index, ss : Integer;
   Count : Integer4;

Begin

   FillArray(TestArray,Size,MaxKey);
   Count := 0;

   CASE SearchType OF
   1: Begin
{   i := 1;
   REPEAT
       FOR j := 0 TO 4 DO
         Write(TestArray[i+j]);
       Writeln;
       i := i + 5;
    UNTIL i >= Size;
  }    FOR j := 1 to NumSearches DO
       Begin
        SearchKey := Trunc (Random * MaxKey);
        ss := SequentialSearch(TestArray,SearchKey,Size); 
   {     Writeln('key= ',SearchKey,'  count= ',ss);  }
        Count := Count + ss;                         
       End;
      Writeln('Avg. comparisons = ',Count/NumSearches:9:0);
      End;

   2: Begin
      QuickSort(TestArray,1,Size);
  { i := 1;
   REPEAT
       FOR j := 0 TO 4 DO
         Write(TestArray[i+j]);
       Writeln;
       i := i + 5;
    UNTIL i >= Size;
 }     FOR j := 1 to NumSearches DO
       Begin
        SearchKey := Trunc (Random * MaxKey);
        binCount := 0;
        BinarySearch(TestArray,SearchKey,1,Size,Index); 
  {      Writeln('key= ',SearchKey,'  count= ',binCount);
   }     Count := Count + binCount;                           

       End;
      Writeln('Avg. comparisons = ',Count/NumSearches:9:0);
      End;

   3: Begin
      QuickSort(TestArray,1,Size);
  { i := 1;
   REPEAT
       FOR j := 0 TO 4 DO
         Write(TestArray[i+j]);
       Writeln;
       i := i + 5;
    UNTIL i >= Size;
   }   FOR j := 1 to NumSearches DO
       Begin
        SearchKey := Trunc (Random * MaxKey);
        binCount := 0;
        BinaryItSearch(TestArray,SearchKey,
             Size,Index,binCount); 
    {    Writeln('key= ',SearchKey,'  count= ',binCount);
     }   Count := Count + binCount;                           


       End;
      Writeln('Avg. comparisons = ',Count/NumSearches:9:0);
      End;
   End;   

End;


   
BEGIN

   Writeln('Seed random number generator');
   Readln(RandNum);

   Again := True;
   Repeat
      Writeln('Array size?');
      Readln(Size);
      Writeln('Key range?');
      Readln(MaxKey);
      Writeln('Number of searches?');
      Readln(NumTests);
      Writeln('1= Seq   2= Bin (rec.)  3= Bin (iter.)');
      Readln(SearchType);
      Test(Size,MaxKey,NumTests,SearchType);
      Writeln;
      Writeln('Another?');
      Readln(Another);
      If (Another <> 'Y') AND (Another <> 'y') Then
         Again := False;
   Until Not Again;

END.