{VERSION 6 0 "IBM INTEL NT" "6.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Headi ng 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "with(Maplets):\nwith(Maplets:-Eleme nts):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "with(plots):" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "NUM:=20:" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 58 "per:=0: comp:=0: x:=[]: x_nach:=[]:\nCurrDir :=currentdir():" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "setoptio ns3d(axes=none, orientation=[92, 138]):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "with(student):" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 12 "Create array" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "CreateAr r:=proc(NUM)\nlocal i,j,xr;\nglobal x,x_nach;\nRandomize():" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "x:=[]:\nx_nach:=[]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 286 "for i from 1 to NUM do\nxr:=rand(0..NUM);\n x:=[x[], xr()];\n x_nach:=[x_nach[],x[i]];\nfor j from 1 to i-1 do\n if (x[ i]=x[j]) then\n xr:=rand(10..NUM+20);\n x[i]:=xr(); \n x_nach[i]:=x[i];\n j:=1;\n end if;\n end do; \+ \nend do:\nend proc:\nCreateArr(NUM);" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 16 "Maplet Functions" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1205 "Change:=proc()\n local x1,i,C;\n global per,comp,a;\n x1:=[]; \n for i from 1 to NUM do\n x1:=[x1[],x_nach[i]];\n end do:\n if (Map lets:-Tools:-Get('RBBubble'('value'))) then \n Maplets:-Tools:-Set('P1 '=Bubble(x1)):\n Maplets:-Tools:-Set('LBubble'('caption')=cat(cat(cat( \"Bubble (\",convert(comp,string)),\n cat(\" ,\", convert(per,string))),\")\")):\n elif (Maplets:-Tools:-Get('RBChoice'( 'value'))) then \n Maplets:-Tools:-Set('P1'=Choice(x1)):\n Maplets:-To ols:-Set('LChoice'('caption')=cat(cat(cat(\"Choice (\",convert(comp,st ring)),\n cat(\" ,\",convert(per,string))),\")\") ):\n elif (Maplets:-Tools:-Get('RBShell'('value'))) then \n Maplets:-T ools:-Set('P1'=Shell(x1)):\n Maplets:-Tools:-Set('LShell'('caption')=c at(cat(cat(\"Shell (\",convert(comp,string)),\n c at(\" ,\",convert(per,string))),\")\")):\n elif (Maplets:-Tools:-Get(' RBHoare'('value'))) then \n per:=0; comp:=0; a:=x1;\n C:=Hoare(1,NUM,t rue,[]);\n Maplets:-Tools:-Set('P1'=display(C,insequence=true)):\n Map lets:-Tools:-Set('LHoare'('caption')=cat(cat(cat(\"Hoare (\",convert(c omp,string)),\n cat(\" ,\",convert(per,string))), \")\")):\n else Display(Maplet([\"Unexpected Error!\"]));\nend if;\nen d proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1511 "ReSort:=proc() \nglobal NUM,per,comp,a,x_nach,x;\nlocal x1,i,C;\nNUM:=Maplets:-Tools: -Get('Sl');\nCreateArr(NUM);\nx_nach:=x;\nMaplets:-Tools:-Set('LBubble '('caption')=\"Bubble (?, ?) \"):\nMaplets:-Tools:-Set('LChoice'('capt ion')=\"Choice (?, ?) \"):\nMaplets:-Tools:-Set('LShell'('caption')=\" Shell (?, ?) \"):\nMaplets:-Tools:-Set('LHoare'('caption')=\"Hoare (?, ?) \"):\n x1:=[];\n for i from 1 to NUM do\n x1:=[x1[],x_nach[i]];\n end do:\n if (Maplets:-Tools:-Get('RBBubble'('value'))) then \n Maple ts:-Tools:-Set('P1'=Bubble(x1)):\n Maplets:-Tools:-Set('LBubble'('capt ion')=cat(cat(cat(\"Bubble (\",convert(comp,string)),\n \+ cat(\" ,\",convert(per,string))),\")\")):\n elif (Maplets:-Tool s:-Get('RBChoice'('value'))) then \n Maplets:-Tools:-Set('P1'=Choice(x 1)):\n Maplets:-Tools:-Set('LChoice'('caption')=cat(cat(cat(\"Choice ( \",convert(comp,string)),\n cat(\" ,\",convert(pe r,string))),\")\")):\n elif (Maplets:-Tools:-Get('RBShell'('value'))) \+ then \n Maplets:-Tools:-Set('P1'=Shell(x1)):\n Maplets:-Tools:-Set('LS hell'('caption')=cat(cat(cat(\"Shell (\",convert(comp,string)),\n \+ cat(\" ,\",convert(per,string))),\")\")):\n elif (Map lets:-Tools:-Get('RBHoare'('value'))) then \n per:=0; comp:=0; a:=x1; \n C:=Hoare(1,NUM,true,[]);\n Maplets:-Tools:-Set('P1'=display(C,inseq uence=true)):\n Maplets:-Tools:-Set('LHoare'('caption')=cat(cat(cat(\" Hoare (\",convert(comp,string)),\n cat(\" ,\",con vert(per,string))),\")\")):\n else Display(Maplet([\"Unexpected Error! \"]));\nend if;\nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 987 "ShowHelp:=proc()\nDisplay(\n Maplet(\n Window(\n title=\"He lp\", width=400, height=400, resizable=false,\n layout=\n BoxLa yout(\n [\"\\t\321\356\360\362\350\360\356\342\352\350\",\n \+ \"\\t\320\340\347\353\350\367\355\373\345 \340\353\343\356\360\350\362 \354\373 \361\356\360\362\350\360\356\342\352\350 \357\360\345\344\361 \362\340\342\353\345\355\373 \342 \344\340\355\355\356\354 \357\360 \350\353\356\346\345\355\350\350. \317\360\345\344\356\361\362\340\342 \353\345\355\340 \342\356\347\354\356\346\355\356\361\362\374 \357\360 \356\361\354\356\362\360\340 \361\340\354\356\343\356 \365\356\344\340 \361\356\360\362\350\360\356\342\352\350 \350 \356\366\345\355\352 \350 \345\345 \375\364\345\352\362\350\342\355\356\361\362\350 \355 \340 \356\361\355\356\342\340\355\350\350 \352\356\353\350\367\345\361 \362\342\340 \357\360\356\350\347\342\345\344\345\355\355\373\365 \356 \357\345\360\340\366\350\351 \361\360\340\342\355\345\355\350\351 \350 \347\340\354\345\355\373.\\n\n\\t\302 \360\345\346\350\354\345 \340 \355\350\354\340\366\350\350 \357\360\345\344\361\362\340\342\353\345 \355 \361\340\354 \365\356\344 \361\356\360\362\350\360\356\342\352 \350. \325\340\360\340\352\362\345\360\350\361\362\350\352\350 \352 \340\346\344\356\351 \361\356\360\362\350\360\356\342\352\350 \347\340 \364\350\352\361\350\360\356\342\340\355\373 \342 \364\356\360\354\340 \362\345 (\312\356\353\350\367\345\361\362\342\356 \356\357\345\360 \340\366\350\351 \361\360\340\342\355\345\355\350\351, \312\356\353 \350\367\345\361\362\342\356 \347\340\354\345\355).\\n\n\\t\316\366 \345\355\352\340 \361\353\356\346\355\356\361\362\350 \352\340\346\344 \356\343\356 \340\353\343\356\360\350\362\354\340 \355\340\365\356\344 \350\354 \357\356 \364\356\360\354\363\353\345: \312\356\353\350\367 \345\361\362\342\356 \347\340\354\345\355 + (\312\356\353\350\367\345 \361\362\342\356 \361\360\340\342\355\345\355\350\351 / 2). \304\340 \355\355\373\345 \365\340\360\340\352\362\345\360\350\361\362\350\352 \350 \355\340\365\356\344\350\354 \357\356 \352\340\346\344\356\354 \363 \354\345\362\356\344\363 \355\340 \354\340\361\361\350\342\340 \365 \360\340\347\355\356\351 \344\353\350\355\373.\\n\n\\t\317\360 \350 \360\340\341\356\362\345 \341\373\353\340 \350\361\357\356\353 \374\347\356\342\340\355\340 \352\355\350\343\340 \304.\312\355\363 \362\340 \\\"The Art of Programming. \322\356\354 3.\\\" \\\"\321\356 \360\362\350\360\356\342\352\340 \350 \357\356\350\361\352 - 2 \350 \347\344.\\\" \302 \352\355\350\343\345 \345\361\362\374 \357\356\353 \355\373\351 \356\341\347\356\360 \352\353\340\361\361\350\367\345\361 \352\350\365 \340\353\343\356\360\350\362\354\356\342 \361\356\360\362 \350\360\356\342\352\350 \350 \357\356\350\361\352\340.\\n\", \n \+ Button(\"OK\",onclick=Shutdown())\n ]\n )\n )\n )\n )\nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 557 "ShowAbout:=proc( )\n Display(\n Maplet(\n Window(\n title=\"About\",resizable=fal se,\n layout=\n BoxLayout(\n [\"\\t\304\340\355\355\356 \345 \357\360\350\353\356\346\345\355\350\345 - \375\362\356\",\n \+ \"\\t\357\360\340\352\362\350\352\363\354 \357\356 \321\317\317.\", \n \"\\t\302\373\357\356\353\355\350\353 \361\362\363\344\345 \355\362 \343\360\363\357\357\373 \317\314-401\",\n \"\\t\324 \340\352\363\353\374\362\345\362\340 \312\356\354\357\374\376\362\345 \360\355\356\351\",\n \"\\t\354\340\362\345\354\340\362\350\352 \350 \327\324 \314\303\323\",\n Label('halign'=center,'valign'=t op,image=Shovkovy),\n \"\\t\330\356\342\352\356\342\373\351 \300 \353\345\352\361\340\355\344\360 \321\345\360\343\345\345\342\350\367 \",\n \"\\t2005. \317\356\367\362\350 \342\361\345 \357\360\340 \342\340 \347\340\371\350\371\345\355\373.\",\n Button(\"OK\",on click=Shutdown())\n ]\n )\n ),\n Image[Shovkovy](cat(Curr Dir,\"\\\\Shovkovy.jpg\"))\n )\n )\nend proc:" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 513 "ShowStat:=proc()\n#--------Statistics-------- ----\nlocal N,x,Est,X,A,ST,x_save;\nglobal comp, exch, NUM, a, x_nach; \nN:=NUM;\nA:=[]; x_save:=x_nach;\nfor NUM from 10 to 20 by 2 do\nCrea teArr(NUM);\ncomp:=0; exch:=0; Est:=[];\n a:=x_nach; SHoare(1,NUM,tru e,[]); Est:=[Est[],exch+round(comp/3)];\n x:=x_nach; SShell(x); Est:= [Est[],exch+round(comp/3)];\n x:=x_nach; SChoice(x); Est:=[Est[],exch +round(comp/3)];\n x:=x_nach; SBubble(x); Est:=[Est[],exch+round(comp /3)];\n X:=convert([Est],matrix):\n ST:=convert(NUM,string);" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 126 " A:=[A[],matrixplot(X, heights=hi stogram, title=cat(cat(\"Number of elements = \",ST),\"\\n\\nBubble \+ Choice Shell Hoare\"))]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 500 "en d do:\nNUM:=N; x_nach:=x_save; \nDisplay(\n Maplet(\n Window(\n \+ title=\"Statistics\",resizable=false,\n layout=\n BoxLayout(\n BoxColumn(\n BoxRow(border=true,\n BoxCell(\"Overall cost s\")\n ),\n BoxRow(border=true,\n BoxCell(\n Plotte r[P2](display(A,insequence=true), continuous=false, background=grey)) \n ),\n BoxRow(border=true,\n BoxCell(\n Button(\" \+ Next \",SetOption(P2('frame_forward')=true)))\n ) \+ \n )\n )\n )\n )\n )\nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 518 "ShowEst:=proc()\n#--------Estimation------------\nlo cal N,x,Est,X,A,ST,ST2,x_save,i;\nglobal comp, exch, NUM, a;\nN:=NUM; \+ x_save:=x_nach;\ncomp:=0; exch:=0; Est:=[];\na:=x_nach;\n SHoare(1,NU M,true,[]); Est:=[Est[],exch+round(comp/3)];\n x:=x_nach; SShell(x); \+ Est:=[Est[],exch+round(comp/3)];\n x:=x_nach; SChoice(x); Est:=[Est[] ,exch+round(comp/3)];\n x:=x_nach; SBubble(x); Est:=[Est[],exch+round (comp/3)];\n X:=convert([Est],matrix):\n ST2:=cat(\"\\n\",convert(Li stTools[Reverse](x_nach),string));\n ST:=convert(NUM,string);" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 129 " A:=matrixplot(X, heights=histogr am, title=cat(cat(cat(\"Number of elements = \",ST),\"\\n\\nBubble C hoice Shell Hoare\"),ST2)):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 457 "NUM:=N; \nDisplay(\n Maplet(\n Window(\n title=\"Estimation\" ,resizable=false,\n layout=\n BoxLayout(\n BoxColumn(\n B oxRow(border=true,\n BoxCell(\"Overall costs\")\n ),\n Bo xRow(border=true,\n BoxCell(\n Plotter[P3](display(A,insequ ence=true), continuous=false, background=grey))\n ),\n BoxRow( border=true,\n BoxCell(\n Button(\" OK \",o nclick=Shutdown()))\n ) \n )\n )\n )\n )\n )\nend proc:" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 11 "Bubble Sort" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Bubble:=p roc(XXX)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 132 "local X,N,A,p,exch,i,j ,a,x,ST;\nglobal comp,per;\nx:=XXX;\nX:=convert([x],matrix):\nST:=cat( \"\\n\",convert(ListTools[Reverse](x),string));" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 90 "A:=[matrixplot(X, heights=histogram, title=cat(\"BUBB LE.\\nComparisons=0 Exchanges=0\",ST))]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 515 "exch:=true:\nN:=0: comp:=0;\nwhile (exch) do\nexch:= false; \nfor i from 1 to (NUM-1) do\n comp:=comp+1;\n if (x[i]>x[i +1]) then\n a:=x[i];\n x[i]:=x[i+1];\n x[i+1]:=a; \n X:=convert([x],matrix);\n N:=N+1;\n ST:=cat(\" \\n\",convert(ListTools[Reverse](x),string));\n A:=[A[],matrixp lot(X, heights=histogram,\n title=cat(cat(cat(\"BUBBLE.\\nCompa risons=\",convert(comp,string)),\n cat(\" Exchanges=\",convert( N,string))),ST) )];\n exch:=true;\n end if;\nend do:\nend do: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 252 "ST:=cat(\"\\n\",convert(ListTo ols[Reverse](x),string));\nA:=[A[],matrixplot(X, heights=histogram,\n \+ title=cat(cat(cat(\"BUBBLE.\\nComparisons=\",convert(comp,stri ng)),\n cat(\" Exchanges=\",convert(N,string))),ST))];\np:=dis play(A,insequence=true):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "per:=N; \nreturn p;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "end proc:" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 11 "Choice Sort" }}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 17 "Choice:=proc(XXX)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "local X,N,A,p,exch,iter,i,a,MAX,mi,x,ST;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 101 "global comp,per;\nx:=XXX;\nX:=convert([x],matrix):\n ST:=cat(\"\\n\",convert(ListTools[Reverse](x),string));" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 90 "A:=[matrixplot(X, heights=histogram, title=cat (\"CHOICE.\\nComparisons=0 Exchanges=0\",ST))]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 676 "exch:=true:\nN:=0: comp:=0; iter:=0:\nwhile (exch) d o\n exch:=false;\n MAX:=x[1]; mi:=1; \n for i from 2 to (NUM-iter) do \n comp:=comp+1; \n if (x[i]>MAX) then MAX:=x[i]; mi:=i; end if; \n end do:\n if (mi<=(NUM-iter)) then\n x[mi]:=x[NUM-iter]; \n x[NUM-iter]:=MAX;\n X:=convert([x],matrix);\n \+ N:=N+1;\n ST:=cat(\"\\n\",convert(ListTools[Reverse](x),str ing));\n A:=[A[],matrixplot(X, heights=histogram,\n ti tle=cat(cat(cat(\"CHOICE.\\nComparisons=\",convert(comp,string)),\n \+ cat(\" Exchanges=\",convert(N,string))),ST))];\n exch:=t rue;\n end if;\niter:=iter+1;\nend do:\nST:=cat(\"\\n\",convert(Lis tTools[Reverse](x),string));" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 199 "A: =[A[],matrixplot(X, heights=histogram,\n title=cat(cat(cat(\"C HOICE.\\nComparisons=\",convert(comp,string)),\n cat(\" Exchan ges=\",convert(N,string))),ST))];\np:=display(A,insequence=true):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "per:=N;\nreturn p;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "end proc:" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 10 "Shell sort" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1549 "Shell:=p roc(XXX)\nlocal kr,kost,k,d,obm,i,perest,A,X,p,x,ST;\nglobal comp,per; \nx:=XXX;\nkr:=ln(NUM)/ln(2);\nkost:=kr - trunc(kr);\nkost:=evalf(kost );\nk:=0; obm:=0; perest:=0; comp:=0:\nX:=convert([x],matrix):\nST:=ca t(\"\\n\",convert(ListTools[Reverse](x),string));\nA:=[matrixplot(X, h eights=histogram, title=cat(\"SHELL.\\nComparisons=0 Exchanges=0\",ST) )]:\nif (kost<0.5) then k:=trunc(kr); else k:=round(kr)-1; end if;\nk: =eval(k);\nd:=round(exp(k*ln(2))-1); d:=eval(d);\nwhile d>0 do\n for i from 1 to (NUM-d) do\n comp:=comp+1;\n if x[i]>x[i+d] then\n ob m:=x[i]; x[i]:=x[i+d]; x[i+d]:=obm; k:=i; perest:=perest+1;\n X:=c onvert([x],matrix);\n A:=[A[],matrixplot(X, heights=histogram,\n \+ title=cat(cat(cat(\"SHELL.\\nComparisons=\",convert(comp,string)), \n cat(\" Exchanges=\",convert(perest,string))),ST))];\n whi le ((k-d>0) and (x[k-d]>x[k])) do\n comp:=comp+1;\n obm:=x[k -d]; x[k-d]:=x[k]; x[k]:=obm; perest:=perest+1;\n X:=convert([x], matrix);\n ST:=cat(\"\\n\",convert(ListTools[Reverse](x),string)) ;\n A:=[A[],matrixplot(X, heights=histogram,\n title=cat(cat (cat(\"SHELL.\\nComparisons=\",convert(comp,string)),\n cat(\" Ex changes=\",convert(perest,string))),ST))];\n k:=k-d;\n end \+ do;\n end if;\n end do;\nd:=round((d-1)/2);\nend do;\nper:=perest;\nS T:=cat(\"\\n\",convert(ListTools[Reverse](x),string));\nA:=[A[],matrix plot(X, heights=histogram,\n title=cat(cat(cat(\"SHELL.\\nCompari sons=\",convert(comp,string)),\n cat(\" Exchanges=\",convert(pere st,string))),ST))];\np:=display(A,insequence=true):\nreturn p;\nend pr oc:" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 10 "Hoare sort" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1019 "Hoare:=proc(l,r,first,AA)\n local A,X,p,i,j,x,y,check,B,ST;\n global per, comp, a;\nA:=AA;\n if first t hen\n X:=convert([a],matrix):\nST:=cat(\"\\n\",convert(ListTools[Rev erse](a),string));\n A:=[matrixplot(X, heights=histogram, title=cat( \"HOARE.\\nComparisons=0 Exchanges=0\",ST))]:\n end if;\n check:=true; \n if (l>=1 and r<=NUM) then\n i:=l; j:=r; x:=a[trunc((l+r)/2)];\n wh ile ((i<=j) or check) do\n check:=false;\n while (a[i]=1) do \+ j:=j-1; comp:=comp+1; end do;\n if i<=j then\n y:=a[i]; a[i]:= a[j]; a[j]:=y;\n i:=i+1; j:=j-1; per:=per+1;\n X:=convert([a ],matrix);\n ST:=cat(\"\\n\",convert(ListTools[Reverse](a),string ));\n A:=[A[],matrixplot(X, heights=histogram,\n title=cat(c at(cat(\"HOARE.\\nComparisons=\",convert(comp,string)),\n cat(\" \+ Exchanges=\",convert(per,string))),ST))];\n end if;\n end do;\n i f l " 0 "" {MPLTEXT 1 0 18 "SBubble:=proc(XXX)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 296 "local N,exch,i,j,a,x,ST;\nglobal comp,per;\nx:=XXX;\nexch:=true: \nN:=0: comp:=0;\nwhile (exch) do\nexch:=false; \nfor i from 1 to (NUM -1) do\n comp:=comp+1;\n if (x[i]>x[i+1]) then\n a:=x[i];\n x[i]:=x[i+1];\n x[i+1]:=a;\n N:=N+1;\n ex ch:=true;\n end if;\nend do:\nend do:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "per:=N;\nend proc:" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 18 "S imple Choice Sort" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "SChoice :=proc(XXX)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "local N,exch,iter,i, a,MAX,mi,x;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 393 "global comp,per;\nx :=XXX;\nexch:=true:\nN:=0: comp:=0; iter:=0:\nwhile (exch) do\n exch:= false;\n MAX:=x[1]; mi:=1; \n for i from 2 to (NUM-iter) do\n comp: =comp+1; \n if (x[i]>MAX) then MAX:=x[i]; mi:=i; end if;\n end do: \n if (mi<=(NUM-iter)) then\n x[mi]:=x[NUM-iter];\n \+ x[NUM-iter]:=MAX;\n N:=N+1;\n exch:=true;\n end if ;\niter:=iter+1;\nend do:\nper:=N;\nend proc:" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 17 "Simple Shell Sort" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 653 "SShell:=proc(XXX)\nlocal kr,kost,k,d,obm,i,perest,X, x;\nglobal comp,per;\nx:=XXX;\nkr:=ln(NUM)/ln(2);\nkost:=kr - trunc(kr );\nkost:=evalf(kost);\nk:=0; obm:=0; perest:=0; comp:=0:\nif (kost<0. 5) then k:=trunc(kr); else k:=round(kr)-1; end if;\nk:=eval(k);\nd:=ro und(exp(k*ln(2))-1); d:=eval(d);\nwhile d>0 do\n for i from 1 to (NUM- d) do\n comp:=comp+1;\n if x[i]>x[i+d] then\n obm:=x[i]; x[i]:=x [i+d]; x[i+d]:=obm; k:=i; perest:=perest+1;\n while ((k-d>0) and \+ (x[k-d]>x[k])) do\n comp:=comp+1;\n obm:=x[k-d]; x[k-d]:=x[k ]; x[k]:=obm; perest:=perest+1;\n k:=k-d;\n end do;\n end \+ if;\n end do;\nd:=round((d-1)/2);\nend do;\nper:=perest;\nend proc:" } }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 17 "Simple Hoare sort" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 539 "SHoare:=proc(l,r,first,AA)\n local A,i,j,x,y,check;\n global per, comp, a;\nA:=AA;\n check:=true;\n if ( l>=1 and r<=NUM) then\n i:=l; j:=r; x:=a[trunc((l+r)/2)];\n while ((i <=j) or check) do\n check:=false;\n while (a[i]=1) do j:=j-1; comp:=comp+1; end do;\n if i<=j then\n y:=a[i]; a[i]:=a[j]; a [j]:=y;\n i:=i+1; j:=j-1; per:=per+1;\n end if;\n end do;\n \+ if l " 0 "" {MPLTEXT 1 0 1886 " M:=Maplet(\n Window(\n title=\"Demonstration of sort methods\",resiza ble=false,\n layout=\n BoxLayout(\n BoxColumn(\n BoxRow(bord er=true,\n BoxCell(\n RadioButton[RBBubble](\"Bubble\",grou p=BG,value=false)\n ),\n BoxCell(\n RadioButton[RBChoi ce](\"Choice\",group=BG,value=true)\n ),\n BoxCell(\n \+ RadioButton[RBShell](\"Shell\",group=BG,value=false)\n ),\n \+ BoxCell(\n RadioButton[RBHoare](\"Hoare\",group=BG,value=false) \n )\n ),\n BoxRow(border=true,\n BoxCell(\n B utton(\"Estimate\",onclick=Evaluate(function=\"ShowEst\"))\n ), \+ \n BoxCell(\n Slider['Sl'](10..20, NUM,onchange='ChangeMas ',\n 'showticks', 'majorticks'=10, 'minorticks'=2,'snapticks'=t rue)\n ),\n BoxCell(\n Button(\"Sort\",SetOption(P1('p lay')=true))\n ) \n ),\n BoxRow(border=true,\n BoxCe ll(\n Plotter[P1](Choice(x), continuous=false, background=grey) \n )\n ),\n BoxRow(border=true,\n BoxCell(\n L abel[LBubble](\"Bubble (?,?)\")\n ),\n BoxCell(\n Labe l[LChoice](cat(cat(cat(\"Choice (\",convert(comp,string)),\n \+ cat(\" ,\",convert(per,string))),\")\"))\n ),\n \+ BoxCell(\n Label[LShell](\"Shell (?,?)\")\n ),\n BoxCe ll(\n Label[LHoare](\"Hoare (?,?)\")\n )\n ),\n Box Row(border=true,\n BoxCell(\n Button(\"Statistics\",onclick =Evaluate(function=\"ShowStat\"))\n ),\n BoxCell(\n Bu tton(\"New\",SetOption(P1('`stop`')=true))\n ),\n BoxCell(\n Button(\"Next frame\",SetOption(P1('frame_forward')=true))\n \+ ),\n BoxCell(\n Button(\"Help\",onclick=Evaluate(functio n=\"ShowHelp\"))\n ),\n BoxCell(\n Button(\"About\",on click=Evaluate(function=\"ShowAbout\"))\n )\n )\n )\n ) \n ),\nButtonGroup[BG](onchange=Evaluate(function=\"Change\")),\nActio n['ChangeMas'](Evaluate(function='ReSort')\n )\n\n):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "Display(M);" }}}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {MARK "8 5 1 0" 18 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }