restart:
with(Maplets):
with(Maplets:-Elements):
with(plots):
NUM:=20:
per:=0: comp:=0: x:=[]: x_nach:=[]:
CurrDir:=currentdir():
setoptions3d(axes=none, orientation=[92, 138]):
with(student):
# Create array
CreateArr:=proc(NUM)
local i,j,xr;
global x,x_nach;
Randomize():
x:=[]:
x_nach:=[]:
for i from 1 to NUM do
xr:=rand(0..NUM);
 x:=[x[],xr()];
 x_nach:=[x_nach[],x[i]];
for j from 1 to i-1 do
     if (x[i]=x[j]) then
          xr:=rand(10..NUM+20);
          x[i]:=xr();
          x_nach[i]:=x[i];
          j:=1;
     end if;
 end do;   
end do:
end proc:
CreateArr(NUM);
# Maplet Functions
Change:=proc()
 local x1,i,C;
 global per,comp,a;
 x1:=[];
 for i from 1 to NUM do
  x1:=[x1[],x_nach[i]];
 end do:
 if (Maplets:-Tools:-Get('RBBubble'('value'))) then 
 Maplets:-Tools:-Set('P1'=Bubble(x1)):
 Maplets:-Tools:-Set('LBubble'('caption')=cat(cat(cat("Bubble (",convert(comp,string)),
                      cat(" ,",convert(per,string))),")")):
 elif (Maplets:-Tools:-Get('RBChoice'('value'))) then 
 Maplets:-Tools:-Set('P1'=Choice(x1)):
 Maplets:-Tools:-Set('LChoice'('caption')=cat(cat(cat("Choice (",convert(comp,string)),
                      cat(" ,",convert(per,string))),")")):
 elif (Maplets:-Tools:-Get('RBShell'('value'))) then 
 Maplets:-Tools:-Set('P1'=Shell(x1)):
 Maplets:-Tools:-Set('LShell'('caption')=cat(cat(cat("Shell (",convert(comp,string)),
                      cat(" ,",convert(per,string))),")")):
 elif (Maplets:-Tools:-Get('RBHoare'('value'))) then 
 per:=0; comp:=0; a:=x1;
 C:=Hoare(1,NUM,true,[]);
 Maplets:-Tools:-Set('P1'=display(C,insequence=true)):
 Maplets:-Tools:-Set('LHoare'('caption')=cat(cat(cat("Hoare (",convert(comp,string)),
                      cat(" ,",convert(per,string))),")")):
 else Display(Maplet(["Unexpected Error!"]));
end if;
end proc:
ReSort:=proc()
global NUM,per,comp,a,x_nach,x;
local x1,i,C;
NUM:=Maplets:-Tools:-Get('Sl');
CreateArr(NUM);
x_nach:=x;
Maplets:-Tools:-Set('LBubble'('caption')="Bubble (?, ?) "):
Maplets:-Tools:-Set('LChoice'('caption')="Choice (?, ?) "):
Maplets:-Tools:-Set('LShell'('caption')="Shell (?, ?) "):
Maplets:-Tools:-Set('LHoare'('caption')="Hoare (?, ?) "):
 x1:=[];
 for i from 1 to NUM do
  x1:=[x1[],x_nach[i]];
 end do:
 if (Maplets:-Tools:-Get('RBBubble'('value'))) then 
 Maplets:-Tools:-Set('P1'=Bubble(x1)):
 Maplets:-Tools:-Set('LBubble'('caption')=cat(cat(cat("Bubble (",convert(comp,string)),
                      cat(" ,",convert(per,string))),")")):
 elif (Maplets:-Tools:-Get('RBChoice'('value'))) then 
 Maplets:-Tools:-Set('P1'=Choice(x1)):
 Maplets:-Tools:-Set('LChoice'('caption')=cat(cat(cat("Choice (",convert(comp,string)),
                      cat(" ,",convert(per,string))),")")):
 elif (Maplets:-Tools:-Get('RBShell'('value'))) then 
 Maplets:-Tools:-Set('P1'=Shell(x1)):
 Maplets:-Tools:-Set('LShell'('caption')=cat(cat(cat("Shell (",convert(comp,string)),
                      cat(" ,",convert(per,string))),")")):
 elif (Maplets:-Tools:-Get('RBHoare'('value'))) then 
 per:=0; comp:=0; a:=x1;
 C:=Hoare(1,NUM,true,[]);
 Maplets:-Tools:-Set('P1'=display(C,insequence=true)):
 Maplets:-Tools:-Set('LHoare'('caption')=cat(cat(cat("Hoare (",convert(comp,string)),
                      cat(" ,",convert(per,string))),")")):
 else Display(Maplet(["Unexpected Error!"]));
end if;
end proc:
ShowHelp:=proc()
Display(
  Maplet(
   Window(
    title="Help", width=400, height=400, resizable=false,
    layout=
     BoxLayout(
      ["\tСортировки",
      "\tРазличные алгоритмы сортировки представлены в данном приложении. Предоставлена возможность просмотра самого хода сортировки и оценки ее эфективности на основании количества произведенных операций сравнений и замены.\n
\tВ режиме анимации представлен сам ход сортировки. Характеристики каждой сортировки зафиксированы в формате (Количество операций сравнений, Количество замен).\n
\tОценка сложности каждого алгоритма находим по формуле: Количество замен + (Количество сравнений / 2). Данные характеристики находим по каждому методу на массивах разной длины.\n
\tПри работе была использована книга Д.Кнута \"The Art of Programming. Том 3.\" \"Сортировка и поиск - 2 изд.\" В книге есть полный обзор классических алгоритмов сортировки и поиска.\n", 
      Button("OK",onclick=Shutdown())
      ]
     )
   )
  )
 )
end proc:
ShowAbout:=proc()
 Display(
  Maplet(
   Window(
    title="About",resizable=false,
    layout=
     BoxLayout(
      ["\tДанное приложение - это",
       "\tпрактикум по СПП.",
       "\tВыполнил студент группы ПМ-401",
       "\tФакультета Компьютерной",
       "\tматематики ЧФ МГУ",
       Label('halign'=center,'valign'=top,image=Shovkovy),
       "\tШовковый Александр Сергеевич",
       "\t2005. Почти все права защищены.",
       Button("OK",onclick=Shutdown())
      ]
     )
   ),
   Image[Shovkovy](cat(CurrDir,"\\Shovkovy.jpg"))
  )
 )
end proc:
ShowStat:=proc()
#--------Statistics------------
local N,x,Est,X,A,ST,x_save;
global comp, exch, NUM, a, x_nach;
N:=NUM;
A:=[]; x_save:=x_nach;
for NUM from 10 to 20 by 2 do
CreateArr(NUM);
comp:=0; exch:=0; Est:=[];
  a:=x_nach; SHoare(1,NUM,true,[]); Est:=[Est[],exch+round(comp/3)];
  x:=x_nach; SShell(x); Est:=[Est[],exch+round(comp/3)];
  x:=x_nach; SChoice(x); Est:=[Est[],exch+round(comp/3)];
  x:=x_nach; SBubble(x); Est:=[Est[],exch+round(comp/3)];
  X:=convert([Est],matrix):
  ST:=convert(NUM,string);
  A:=[A[],matrixplot(X, heights=histogram, title=cat(cat("Number of elements = ",ST),"\n\nBubble   Choice   Shell   Hoare"))]:
end do:
NUM:=N; x_nach:=x_save;   
Display(
  Maplet(
   Window(
    title="Statistics",resizable=false,
    layout=
    BoxLayout(
    BoxColumn(
     BoxRow(border=true,
      BoxCell("Overall costs")
     ),
     BoxRow(border=true,
      BoxCell(
       Plotter[P2](display(A,insequence=true), continuous=false, background=grey))
     ),
     BoxRow(border=true,
      BoxCell(
       Button("         Next         ",SetOption(P2('frame_forward')=true)))
     ) 
    )
    )
   )
  )
 )
end proc:
ShowEst:=proc()
#--------Estimation------------
local N,x,Est,X,A,ST,ST2,x_save,i;
global comp, exch, NUM, a;
N:=NUM; x_save:=x_nach;
comp:=0; exch:=0; Est:=[];
a:=x_nach;
  SHoare(1,NUM,true,[]); Est:=[Est[],exch+round(comp/3)];
  x:=x_nach; SShell(x); Est:=[Est[],exch+round(comp/3)];
  x:=x_nach; SChoice(x); Est:=[Est[],exch+round(comp/3)];
  x:=x_nach; SBubble(x); Est:=[Est[],exch+round(comp/3)];
  X:=convert([Est],matrix):
  ST2:=cat("\n",convert(ListTools[Reverse](x_nach),string));
  ST:=convert(NUM,string);
  A:=matrixplot(X, heights=histogram, title=cat(cat(cat("Number of elements = ",ST),"\n\nBubble   Choice   Shell   Hoare"),ST2)):
NUM:=N;   
Display(
  Maplet(
   Window(
    title="Estimation",resizable=false,
    layout=
    BoxLayout(
    BoxColumn(
     BoxRow(border=true,
      BoxCell("Overall costs")
     ),
     BoxRow(border=true,
      BoxCell(
       Plotter[P3](display(A,insequence=true), continuous=false, background=grey))
     ),
     BoxRow(border=true,
      BoxCell(
       Button("         OK         ",onclick=Shutdown()))
     ) 
    )
    )
   )
  )
 )
end proc:
# 
# Bubble Sort
Bubble:=proc(XXX)
local X,N,A,p,exch,i,j,a,x,ST;
global comp,per;
x:=XXX;
X:=convert([x],matrix):
ST:=cat("\n",convert(ListTools[Reverse](x),string));
A:=[matrixplot(X, heights=histogram, title=cat("BUBBLE.\nComparisons=0 Exchanges=0",ST))]:
exch:=true:
N:=0: comp:=0;
while (exch) do
exch:=false; 
for i from 1 to (NUM-1) do
   comp:=comp+1;
   if (x[i]>x[i+1]) then
        a:=x[i];
        x[i]:=x[i+1];
        x[i+1]:=a;
        X:=convert([x],matrix);
        N:=N+1;
        ST:=cat("\n",convert(ListTools[Reverse](x),string));
        A:=[A[],matrixplot(X, heights=histogram,
        title=cat(cat(cat("BUBBLE.\nComparisons=",convert(comp,string)),
        cat(" Exchanges=",convert(N,string))),ST) )];
        exch:=true;
   end if;
end do:
end do:
ST:=cat("\n",convert(ListTools[Reverse](x),string));
A:=[A[],matrixplot(X, heights=histogram,
         title=cat(cat(cat("BUBBLE.\nComparisons=",convert(comp,string)),
         cat(" Exchanges=",convert(N,string))),ST))];
p:=display(A,insequence=true):
per:=N;
return p;
end proc:
# Choice Sort
Choice:=proc(XXX)
local X,N,A,p,exch,iter,i,a,MAX,mi,x,ST;
global comp,per;
x:=XXX;
X:=convert([x],matrix):
ST:=cat("\n",convert(ListTools[Reverse](x),string));
A:=[matrixplot(X, heights=histogram, title=cat("CHOICE.\nComparisons=0 Exchanges=0",ST))]:
exch:=true:
N:=0: comp:=0; iter:=0:
while (exch) do
 exch:=false;
 MAX:=x[1]; mi:=1; 
 for i from 2 to (NUM-iter) do
    comp:=comp+1; 
    if (x[i]>MAX) then MAX:=x[i]; mi:=i; end if;
 end do:
    if (mi<=(NUM-iter)) then
         x[mi]:=x[NUM-iter];
         x[NUM-iter]:=MAX;
         X:=convert([x],matrix);
         N:=N+1;
         ST:=cat("\n",convert(ListTools[Reverse](x),string));
         A:=[A[],matrixplot(X, heights=histogram,
         title=cat(cat(cat("CHOICE.\nComparisons=",convert(comp,string)),
         cat(" Exchanges=",convert(N,string))),ST))];
         exch:=true;
    end if;
iter:=iter+1;
end do:
ST:=cat("\n",convert(ListTools[Reverse](x),string));
A:=[A[],matrixplot(X, heights=histogram,
         title=cat(cat(cat("CHOICE.\nComparisons=",convert(comp,string)),
         cat(" Exchanges=",convert(N,string))),ST))];
p:=display(A,insequence=true):
per:=N;
return p;
end proc:
# Shell sort
Shell:=proc(XXX)
local kr,kost,k,d,obm,i,perest,A,X,p,x,ST;
global comp,per;
x:=XXX;
kr:=ln(NUM)/ln(2);
kost:=kr - trunc(kr);
kost:=evalf(kost);
k:=0; obm:=0; perest:=0; comp:=0:
X:=convert([x],matrix):
ST:=cat("\n",convert(ListTools[Reverse](x),string));
A:=[matrixplot(X, heights=histogram, title=cat("SHELL.\nComparisons=0 Exchanges=0",ST))]:
if (kost<0.5) then k:=trunc(kr); else k:=round(kr)-1; end if;
k:=eval(k);
d:=round(exp(k*ln(2))-1); d:=eval(d);
while d>0 do
 for i from 1 to (NUM-d) do
  comp:=comp+1;
  if x[i]>x[i+d] then
     obm:=x[i]; x[i]:=x[i+d]; x[i+d]:=obm; k:=i; perest:=perest+1;
     X:=convert([x],matrix);
     A:=[A[],matrixplot(X, heights=histogram,
     title=cat(cat(cat("SHELL.\nComparisons=",convert(comp,string)),
      cat(" Exchanges=",convert(perest,string))),ST))];
      while ((k-d>0) and (x[k-d]>x[k])) do
      comp:=comp+1;
      obm:=x[k-d]; x[k-d]:=x[k]; x[k]:=obm; perest:=perest+1;
      X:=convert([x],matrix);
      ST:=cat("\n",convert(ListTools[Reverse](x),string));
      A:=[A[],matrixplot(X, heights=histogram,
      title=cat(cat(cat("SHELL.\nComparisons=",convert(comp,string)),
      cat(" Exchanges=",convert(perest,string))),ST))];
        k:=k-d;
     end do;
  end if;
 end do;
d:=round((d-1)/2);
end do;
per:=perest;
ST:=cat("\n",convert(ListTools[Reverse](x),string));
A:=[A[],matrixplot(X, heights=histogram,
      title=cat(cat(cat("SHELL.\nComparisons=",convert(comp,string)),
      cat(" Exchanges=",convert(perest,string))),ST))];
p:=display(A,insequence=true):
return p;
end proc:
# Hoare sort
Hoare:=proc(l,r,first,AA)
 local A,X,p,i,j,x,y,check,B,ST;
 global per, comp, a;
A:=AA;
 if first then
   X:=convert([a],matrix):
ST:=cat("\n",convert(ListTools[Reverse](a),string));
   A:=[matrixplot(X, heights=histogram, title=cat("HOARE.\nComparisons=0 Exchanges=0",ST))]:
 end if;
 check:=true;
 if (l>=1 and r<=NUM) then
 i:=l; j:=r; x:=a[trunc((l+r)/2)];
  while ((i<=j) or check) do
    check:=false;
    while (a[i]<x and i<=NUM) do i:=i+1; comp:=comp+1; end do;
    while (x<a[j] and j>=1) do j:=j-1; comp:=comp+1; end do;
    if i<=j then
      y:=a[i]; a[i]:=a[j]; a[j]:=y;
      i:=i+1; j:=j-1; per:=per+1;
      X:=convert([a],matrix);
      ST:=cat("\n",convert(ListTools[Reverse](a),string));
      A:=[A[],matrixplot(X, heights=histogram,
      title=cat(cat(cat("HOARE.\nComparisons=",convert(comp,string)),
      cat(" Exchanges=",convert(per,string))),ST))];
    end if;
  end do;
  if l<j then A:=Hoare(l,j,false,A); end if;
  if i<r then A:=Hoare(i,r,false,A); end if;
  end if;
return A;
end proc:
# Simple Bubble Sort
SBubble:=proc(XXX)
local N,exch,i,j,a,x,ST;
global comp,per;
x:=XXX;
exch:=true:
N:=0: comp:=0;
while (exch) do
exch:=false; 
for i from 1 to (NUM-1) do
   comp:=comp+1;
   if (x[i]>x[i+1]) then
        a:=x[i];
        x[i]:=x[i+1];
        x[i+1]:=a;
        N:=N+1;
        exch:=true;
   end if;
end do:
end do:
per:=N;
end proc:
# Simple Choice Sort
SChoice:=proc(XXX)
local N,exch,iter,i,a,MAX,mi,x;
global comp,per;
x:=XXX;
exch:=true:
N:=0: comp:=0; iter:=0:
while (exch) do
 exch:=false;
 MAX:=x[1]; mi:=1; 
 for i from 2 to (NUM-iter) do
    comp:=comp+1; 
    if (x[i]>MAX) then MAX:=x[i]; mi:=i; end if;
 end do:
    if (mi<=(NUM-iter)) then
         x[mi]:=x[NUM-iter];
         x[NUM-iter]:=MAX;
         N:=N+1;
         exch:=true;
    end if;
iter:=iter+1;
end do:
per:=N;
end proc:
# Simple Shell Sort
SShell:=proc(XXX)
local kr,kost,k,d,obm,i,perest,X,x;
global comp,per;
x:=XXX;
kr:=ln(NUM)/ln(2);
kost:=kr - trunc(kr);
kost:=evalf(kost);
k:=0; obm:=0; perest:=0; comp:=0:
if (kost<0.5) then k:=trunc(kr); else k:=round(kr)-1; end if;
k:=eval(k);
d:=round(exp(k*ln(2))-1); d:=eval(d);
while d>0 do
 for i from 1 to (NUM-d) do
  comp:=comp+1;
  if x[i]>x[i+d] then
     obm:=x[i]; x[i]:=x[i+d]; x[i+d]:=obm; k:=i; perest:=perest+1;
      while ((k-d>0) and (x[k-d]>x[k])) do
      comp:=comp+1;
      obm:=x[k-d]; x[k-d]:=x[k]; x[k]:=obm; perest:=perest+1;
        k:=k-d;
     end do;
  end if;
 end do;
d:=round((d-1)/2);
end do;
per:=perest;
end proc:
# Simple Hoare sort
SHoare:=proc(l,r,first,AA)
 local A,i,j,x,y,check;
 global per, comp, a;
A:=AA;
 check:=true;
 if (l>=1 and r<=NUM) then
 i:=l; j:=r; x:=a[trunc((l+r)/2)];
  while ((i<=j) or check) do
    check:=false;
    while (a[i]<x and i<=NUM) do i:=i+1; comp:=comp+1; end do;
    while (x<a[j] and j>=1) do j:=j-1; comp:=comp+1; end do;
    if i<=j then
      y:=a[i]; a[i]:=a[j]; a[j]:=y;
      i:=i+1; j:=j-1; per:=per+1;
    end if;
  end do;
  if l<j then Hoare(l,j,false,A); end if;
  if i<r then Hoare(i,r,false,A); end if;
  end if;
end proc:
# Show the Maplet
M:=Maplet(
 Window(
  title="Demonstration of sort methods",resizable=false,
  layout=
   BoxLayout(
    BoxColumn(
     BoxRow(border=true,
      BoxCell(
       RadioButton[RBBubble]("Bubble",group=BG,value=false)
      ),
      BoxCell(
       RadioButton[RBChoice]("Choice",group=BG,value=true)
      ),
      BoxCell(
       RadioButton[RBShell]("Shell",group=BG,value=false)
      ),
      BoxCell(
       RadioButton[RBHoare]("Hoare",group=BG,value=false)
      )
     ),
     BoxRow(border=true,
      BoxCell(
       Button("Estimate",onclick=Evaluate(function="ShowEst"))
      ), 
      BoxCell(
        Slider['Sl'](10..20, NUM,onchange='ChangeMas',
        'showticks', 'majorticks'=10, 'minorticks'=2,'snapticks'=true)
      ),
      BoxCell(
       Button("Sort",SetOption(P1('play')=true))
      ) 
     ),
     BoxRow(border=true,
      BoxCell(
       Plotter[P1](Choice(x), continuous=false, background=grey)
      )
     ),
     BoxRow(border=true,
      BoxCell(
       Label[LBubble]("Bubble (?,?)")
      ),
      BoxCell(
       Label[LChoice](cat(cat(cat("Choice (",convert(comp,string)),
                      cat(" ,",convert(per,string))),")"))
      ),
      BoxCell(
       Label[LShell]("Shell (?,?)")
      ),
      BoxCell(
       Label[LHoare]("Hoare (?,?)")
      )
     ),
     BoxRow(border=true,
      BoxCell(
       Button("Statistics",onclick=Evaluate(function="ShowStat"))
      ),
      BoxCell(
       Button("New",SetOption(P1('`stop`')=true))
      ),
      BoxCell(
       Button("Next frame",SetOption(P1('frame_forward')=true))
      ),
      BoxCell(
       Button("Help",onclick=Evaluate(function="ShowHelp"))
      ),
      BoxCell(
       Button("About",onclick=Evaluate(function="ShowAbout"))
      )
     )
    )
   )
 ),
ButtonGroup[BG](onchange=Evaluate(function="Change")),
Action['ChangeMas'](Evaluate(function='ReSort')
 )

):
Display(M);