program sortowanie;

{$APPTYPE CONSOLE}

uses
  SysUtils,
  windows;

var
zakres,srod,x,n,o,q,i,z:longint;

   S,A:array[1..1000000] of Longint;
     B:array[1..3] of Longint;
                  start1,stop1:Double;
                  timeEnd,TimeStart,freq,timestart1,timeend1:Int64;
                  czas:extended;
F:textfile;

procedure quicksortS(start,stop:longint);
var
h,i,j,x:longint;
BEgin
i:=start;
j:=stop;
x:=A[ (start+stop) div 2];

repeat
while (a[j]>x) do  j:=j-1;
 while (a[i]<x) do  i:=i+1;
if (i<=j)
  then
	BEgin
    h:=a[i];
    a[i]:=a[j];
    a[j]:=h;
    j:=j-1;
    i:=i+1;
  End;

until (i>=j);

    if (start<j) then quicksortS(start, j);
    if (i<stop) then quicksortS(i, stop);
end;

procedure quicksortP(start,stop:longint);
var
x,h,i,j:longint;
BEgin
i:=start;
j:=stop;
x:=A[stop];

repeat
while (a[j]>x) do  j:=j-1;
 while (a[i]<x) do  i:=i+1;
if (i<=j)
  then
	BEgin
    h:=a[i];
    a[i]:=a[j];
    a[j]:=h;
    j:=j-1;
    i:=i+1;
  End;

until (i>=j);
    if (start<j) then quicksortP(start, j);
    if (i<stop) then quicksortP(i, stop);
end;



procedure quicksortM(start,stop:longint);
var
x,h,i,j:longint;
BEgin
//for z:=1 to 3 do B[z]:=random(n)+1;

i:=start;
j:=stop;
  for z:=1 to 3 do
  Begin
    B[z]:= random(stop-start+1)+start;
 //   Writeln('z ',B[z],' A[B[z]] ',A[B[z]]);
  end;
  //writeln;
if ((A[B[1]] >= A[B[2]]) and (A[B[1]] <= A[B[3]])) or ((A[B[1]] <= A[B[2]])) and (A[B[1]] >= A[B[3]]) then x:=A[B[1]];
if ((A[B[1]] >= A[B[2]]) and (A[B[3]] <= A[B[2]])) or ((A[B[1]] <= A[B[2]])) and (A[B[3]] >= A[B[2]]) then x:=A[B[2]];
if ((A[B[1]] >= A[B[3]]) and (A[B[2]] <= A[B[3]])) or ((A[B[1]] <= A[B[3]]) and (A[B[2]] >= A[B[3]])) then x:=A[B[3]];


//Writeln('x ', x, 'z ',z);
repeat

while (a[j]>x) do  j:=j-1;
 while (a[i]<x) do  i:=i+1;
if (i<=j)
  then
	BEgin
    h:=a[i];
    a[i]:=a[j];
    a[j]:=h;
    j:=j-1;
    i:=i+1;
  End;

until (i>=j);
    if (start<j) then quicksortM(start, j);
    if (i<stop) then quicksortM(i, stop);
end;



procedure quicksort(start,stop:longint);
var
h,i,j:longint;
BEgin
i:=start;
j:=stop;
x:=A[start];

repeat
while (a[j]>x) do  j:=j-1;
 while (a[i]<x) do  i:=i+1;
if (i<=j)
  then
	BEgin
    h:=a[i];
    a[i]:=a[j];
    a[j]:=h;
    j:=j-1;
    i:=i+1;
  End;

until (i>=j);


    if (start<j) then quicksort(start, j);
    if (i<stop) then quicksort(i, stop);
end;

Procedure losowe;
begin
AssignFile(f,'losoweQ.txt');
Rewrite(f);
Close(f);


writeln('podaj n');
readln(n);
Writeln('podaj zakres');
readln(zakres);

AssignFile(f,'losoweQ.txt');
Reset(F);
Append(f);
Writeln(F,'Liczba n    Quick-Prawy                       Quick-srodkowy                  Quick-mediana');
CloseFile(F);

repeat
AssignFile(f,'losoweQ.txt');
Reset(f);
Append(F);
Write(F,n,'  ');
z:=z+1;
Writeln(n);
for i:=1 to n do
 begin
 S[i]:=random(zakres)+random(zakres);
 //Write(S[i],' ');
 A[i]:=S[i];
 end;
writeln;

if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
QuicksortP(1,n);


QueryPerformanceCounter(TimeEnd);
czas:=(TimeEnd-TimeStart)/Freq*1000;
writeln('qP :',czas);
Write(F,'  ',czas,'   ');
    for i:=1 to n do
  begin
  // write(A[i],' ');
  end;

for i:=1 to n do
  begin
  a[i]:=S[i];
  //write(A[i],' ');
  end;
if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
quicksortS(1,n);
QueryPerformanceCounter(TimeEnd);
czas:=(TimeEnd-TimeStart)/Freq*1000;
writeln('qS :',czas);
Write(F,'  ',czas,'  ');
//for i:=1 to n do
 //begin
// write(T[i],' ');
// end;

for i:=1 to n do
  begin
  a[i]:=S[i];
 // write(A[i],' ');
  end;
if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
quicksortM(1,n);
QueryPerformanceCounter(TimeEnd);
czas:=(TimeEnd-TimeStart)/Freq*1000;
writeln('qM :',czas);
Writeln(F,'  ',czas,'  ');
CloseFile(F);
n:=n+5000;
until  n>60000;
//z=2;
//n>100000

  { TODO -oUser -cConsole Main : Insert code here }
end;


Procedure mal;

begin
AssignFile(f,'malQ.txt');
Rewrite(f);
Close(f);


writeln('podaj n');
readln(n);


AssignFile(f,'malQ.txt');
Reset(F);
Append(f);
Writeln(F,'Liczba n    Quick-Prawy                       Quick-srodkowy                  Quick-mediana');
CloseFile(F);

repeat
AssignFile(f,'malQ.txt');
Reset(f);
Append(F);
Write(F,n,'  ');
z:=z+1;
Writeln(n);
 for i:=1 to n do
  BEgin
  A[i]:=(n-i) +1 ;
 // Write(a[i],' ');
  end;
if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
QuicksortP(1,n);
QueryPerformanceCounter(TimeEnd);
czas:=(TimeEnd-TimeStart)/Freq*1000;
writeln('qP :',czas);
Write(F,'  ',czas,'   ');
//Write(F,'niedzialaaaaaaaaaaa          ');
 for i:=1 to n do
  BEgin
  A[i]:=(n-i) +1 ;
 // Write(a[i],' ');
  end;
if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
QuicksortS(1,n);
QueryPerformanceCounter(TimeEnd);
czas:=(TimeEnd-TimeStart)/Freq*1000;
writeln('qS :',czas);
Write(F,'  ',czas,'   ');
    for i:=1 to n do
  BEgin
  A[i]:=(n-i) +1 ;
 // Write(a[i],' ');
  end;
if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
QuicksortM(1,n);
QueryPerformanceCounter(TimeEnd);
czas:=(TimeEnd-TimeStart)/Freq*1000;
writeln('qM :',czas);
Writeln(F,'  ',czas,'   ');
CloseFile(F);

n:=n+1000;

until  n>47000;

  { TODO -oUser -cConsole Main : Insert code here }
end;
Procedure staly;

begin
AssignFile(f,'stalQ.txt');
Rewrite(f);
Close(f);


writeln('podaj n');
readln(n);


AssignFile(f,'stalQ.txt');
Reset(F);
Append(f);
Writeln(F,'Liczba n    Quick-Prawy                       Quick-srodkowy                  Quick-mediana');
CloseFile(F);

repeat
AssignFile(f,'stalQ.txt');
Reset(f);
Append(F);
Write(F,n,'  ');
q:=10;
Writeln(n);
 for i:=1 to n do
  BEgin
  A[i]:=q ;
 // Write(a[i],' ');
  end;
if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
QuicksortP(1,n);
QueryPerformanceCounter(TimeEnd);
czas:=(TimeEnd-TimeStart)/Freq*1000;
writeln('qP :',czas);
Write(F,'  ',czas,'   ');
 for i:=1 to n do
  BEgin
  A[i]:=q ;
 // Write(a[i],' ');
  end;
if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
QuicksortS(1,n);
QueryPerformanceCounter(TimeEnd);
czas:=(TimeEnd-TimeStart)/Freq*1000;
writeln('qS :',czas);
Write(F,'  ',czas,'   ');
    for i:=1 to n do
  BEgin
  A[i]:=q ;
 // Write(a[i],' ');
  end;
if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
QuicksortM(1,n);
QueryPerformanceCounter(TimeEnd);
czas:=(TimeEnd-TimeStart)/Freq*1000;
writeln('qM :',czas);
Writeln(F,'  ',czas,'   ');
CloseFile(F);

n:=n+5000;

until  n>60000;


  { TODO -oUser -cConsole Main : Insert code here }
end;




Procedure aksztalt;
var
n,i,z,q:Longint;
begin
AssignFile(f,'Aksztalt.txt');
Rewrite(f);
Close(f);


writeln('podaj n');
readln(n);


AssignFile(f,'Aksztalt.txt');
Reset(F);
Append(f);
Writeln(F,'Liczba n    Quick-Prawy                       Quick-srodkowy                  Quick-mediana');
CloseFile(F);

repeat
AssignFile(f,'Aksztalt.txt');
Reset(f);
Append(F);
Write(F,n,'  ');
Writeln(n);
                //tworzenie tablicy a-ksztaltnej
q:=1;
for z:=1 to (n div 2) do
  Begin
   A[z]:=q;
   S[z]:=A[z];
   q:=q+2;
  // write(a[z],' ');
 End;

 q:=q-1;
 for z:=(n div 2)+1 to n do
  Begin
   A[z]:=q;
   S[z]:=q-2;
   q:=q-2;
   //Write(a[z],' ');
  End ;
 

if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
QuicksortP(1,n);
QueryPerformanceCounter(TimeEnd);
czas:=(TimeEnd-TimeStart)/Freq*1000;
writeln('qP :',czas);
Write(F,'  ',czas,'   ');
 for z:=1 to n do
  BEgin
  A[z]:=S[z] ;
 // Write(a[i],' ');
  end;

if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
QuicksortS(1,n);                    // atu mi sie wywala dla srodkowego elementu.
QueryPerformanceCounter(TimeEnd);
czas:=(TimeEnd-TimeStart)/Freq*1000;
writeln('qS :',czas);
Write(F,'  ',czas,'   ');
    for z:=1 to n do
  BEgin
  A[z]:=S[z] ;
 // Write(a[i],' ');
  end;
if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
QuicksortM(1,n);
QueryPerformanceCounter(TimeEnd);
czas:=(TimeEnd-TimeStart)/Freq*1000;
writeln('qM :',czas);
Writeln(F,'  ',czas,'   ');
CloseFile(F);
//for i:=1 to n do Write(a[i],' ');
n:=n+50000;

until  n>600000;


  { TODO -oUser -cConsole Main : Insert code here }
end;







BEGIN
mal;
//staly;
//losowy
//aksztalt;

{readln(n);

 q:=1;
 srod:=n div 2;
for z:=1 to (n div 2) do
  Begin
   A[z]:=q;
   S[z]:=A[z];
   q:=q+2;
   //write(a[z],' ');
 End;
 q:=q-1;
 for z:=(n div 2)+1 to n do
  Begin
  q:=q-2;
   A[z]:=q;
   S[z]:=A[z];
  //Write(a[z],' ');

  End ;     if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
QuicksortS(1,n);                    // atu mi sie wywala dla srodkowego elementu.
QueryPerformanceCounter(TimeEnd);
czas:=(TimeEnd-TimeStart)/Freq*1000;
writeln('qS :',czas);
readln;
  for z:=1 to n do
  BEgin
  //A[z]:=S[z] ;
 //Write(a[z],' ');
  end;}

readln;
END.