5-sortnet/sortnet.mp

   1 %defaultfont:="csr12";
   2 %verbatimtex \input twelvecs etex
   3 u:=1 ;
   4 ahlength:=u*3;
   5
   6 beginfig(0);
   7 v:=u*7mm;
   8
   9 z12=(1v,1v);
  10 z13=(2v,1v);
  11 z21=(0v,2v);
  12 z22=(1v,2v);
  13 z23=(2v,2v);
  14 z24=(3v,2v);
  15 z31=(0v,4v);
  16 z32=(1v,4v);
  17 z33=(2v,4v);
  18 z34=(3v,4v);
  19 z42=(1v,5v);
  20 z43=(2v,5v);
  21
  22 pickup pencircle scaled 0.4pt;
  23 draw(z21--z22--z23--z24--z34--z33--z32--z31--z21);
  24 drawarrow(z22--z12);
  25 drawarrow(z23--z13);
  26 drawarrow(z42--z32);
  27 drawarrow(z43--z33);
  28
  29 label.bot(btex \strut a etex,z32);
  30 label.bot(btex \strut b etex,z33);
  31 label.top(btex min etex,z22);
  32 label.top(btex max etex,z23);
  33
  34
  35 endfig;
  36
  37 beginfig(1);
  38 v:=u*5mm;
  39 z10=(0v,0v);
  40 z20=(2v,0v);
  41 z30=(4v,0v);
  42 z40=(6v,0v);
  43 z50=(8v,0v);
  44
  45 z11=(0v,1v);
  46 z12=(0v,2v);
  47 z13=(0v,3v);
  48 z14=(0v,4v);
  49 z15=(0v,5v);
  50 z16=(0v,6v);
  51 z17=(0v,7v);
  52 z18=(0v,8v);
  53 z19=(0v,9v);
  54 z110=(0v,10v);
  55
  56 z21=(2v,1v);
  57 z22=(2v,2v);
  58 z23=(2v,3v);
  59 z24=(2v,4v);
  60 z25=(2v,5v);
  61 z26=(2v,6v);
  62 z27=(2v,7v);
  63 z28=(2v,8v);
  64 z29=(2v,9v);
  65 z210=(2v,10v);
  66
  67 z31=(4v,1v);
  68 z32=(4v,2v);
  69 z33=(4v,3v);
  70 z34=(4v,4v);
  71 z35=(4v,5v);
  72 z36=(4v,6v);
  73 z37=(4v,7v);
  74 z38=(4v,8v);
  75 z39=(4v,9v);
  76 z310=(4v,10v);
  77
  78 z41=(6v,1v);
  79 z42=(6v,2v);
  80 z43=(6v,3v);
  81 z44=(6v,4v);
  82 z45=(6v,5v);
  83 z46=(6v,6v);
  84 z47=(6v,7v);
  85 z48=(6v,8v);
  86 z49=(6v,9v);
  87 z410=(6v,10v);
  88
  89 z51=(8v,1v);
  90 z52=(8v,2v);
  91 z53=(8v,3v);
  92 z54=(8v,4v);
  93 z55=(8v,5v);
  94 z56=(8v,6v);
  95 z57=(8v,7v);
  96 z58=(8v,8v);
  97 z59=(8v,9v);
  98 z510=(8v,10v);
  99
 100 z111=(0v,11v);
 101 z211=(2v,11v);
 102 z311=(4v,11v);
 103 z411=(6v,11v);
 104 z511=(8v,11v);
 105
 106 z1015=(-1v,1.5v);
 107 z1615=(9v,1.5v);
 108 z1035=(-1v,3.5v);
 109 z1635=(9v,3.5v);
 110 z1065=(-1v,6.5v);
 111 z1665=(9v,6.5v);
 112
 113 pickup pencircle scaled 0.4pt;
 114 draw(z10--z111);
 115 draw(z20--z211);
 116 draw(z30--z311);
 117 draw(z40--z411);
 118 draw(z50--z511);
 119 drawarrow(z11--z21);
 120 drawarrow(z13--z23);
 121 drawarrow(z16--z26);
 122 drawarrow(z110--z210);
 123 drawarrow(z22--z32);
 124 drawarrow(z25--z35);
 125 drawarrow(z29--z39);
 126 drawarrow(z34--z44);
 127 drawarrow(z38--z48);
 128 drawarrow(z47--z57);
 129
 130 pickup pencircle scaled 0.7pt;
 131 draw(z1015--z1615) dashed withdots scaled 0.7;
 132 draw(z1035--z1635) dashed withdots scaled 0.7;
 133 draw(z1065--z1665) dashed withdots scaled 0.7;
 134
 135 label.top(btex x1 etex,z111);
 136 label.top(btex x2 etex,z211);
 137 label.top(btex x3 etex,z311);
 138 label.top(btex x4 etex,z411);
 139 label.top(btex x5 etex,z511);
 140
 141 endfig;
 142
 143 beginfig(2);
 144 v:=u*5mm;
 145 z13=(0v,3v);
 146 z23=(2v,3v);
 147 z33=(4v,3v);
 148 z43=(6v,3v);
 149 z53=(8v,3v);
 150
 151 z14=(0v,4v);
 152 z15=(0v,5v);
 153 z16=(0v,6v);
 154 z17=(0v,7v);
 155 z18=(0v,8v);
 156 z19=(0v,9v);
 157 z110=(0v,10v);
 158
 159 z24=(2v,4v);
 160 z25=(2v,5v);
 161 z26=(2v,6v);
 162 z27=(2v,7v);
 163 z28=(2v,8v);
 164 z29=(2v,9v);
 165 z210=(2v,10v);
 166
 167 z34=(4v,4v);
 168 z35=(4v,5v);
 169 z36=(4v,6v);
 170 z37=(4v,7v);
 171 z38=(4v,8v);
 172 z39=(4v,9v);
 173 z310=(4v,10v);
 174
 175 z44=(6v,4v);
 176 z45=(6v,5v);
 177 z46=(6v,6v);
 178 z47=(6v,7v);
 179 z48=(6v,8v);
 180 z49=(6v,9v);
 181 z410=(6v,10v);
 182
 183 z54=(8v,4v);
 184 z55=(8v,5v);
 185 z56=(8v,6v);
 186 z57=(8v,7v);
 187 z58=(8v,8v);
 188 z59=(8v,9v);
 189 z510=(8v,10v);
 190
 191 z111=(0v,11v);
 192 z211=(2v,11v);
 193 z311=(4v,11v);
 194 z411=(6v,11v);
 195 z511=(8v,11v);
 196
 197 pickup pencircle scaled 0.4pt;
 198 draw(z13--z111);
 199 draw(z23--z211);
 200 draw(z33--z311);
 201 draw(z43--z411);
 202 draw(z53--z511);
 203 drawarrow(z14--z24);
 204 drawarrow(z16--z26);
 205 drawarrow(z18--z28);
 206 drawarrow(z110--z210);
 207 drawarrow(z25--z35);
 208 drawarrow(z27--z37);
 209 drawarrow(z29--z39);
 210 drawarrow(z36--z46);
 211 drawarrow(z38--z48);
 212 drawarrow(z47--z57);
 213
 214 label.top(btex x1 etex,z111);
 215 label.top(btex x2 etex,z211);
 216 label.top(btex x3 etex,z311);
 217 label.top(btex x4 etex,z411);
 218 label.top(btex x5 etex,z511);
 219
 220 endfig;
 221
 222
 223 beginfig(3);
 224 v:=u*5mm;
 225
 226 z10=(0v,0v);
 227 z15=(0v,5v);
 228 z16=(0v,6v);
 229
 230 z20=(2v,0v);
 231 z24=(2v,4v);
 232 z26=(2v,6v);
 233
 234 z30=(4v,0v);
 235 z33=(4v,3v);
 236 z36=(4v,6v);
 237
 238 z40=(6v,0v);
 239 z42=(6v,2v);
 240 z46=(6v,6v);
 241
 242 z50=(8v,0v);
 243 z51=(8v,1v);
 244 z56=(8v,6v);
 245
 246 z60=(10v,0v);
 247 z65=(10v,5v);
 248 z66=(10v,6v);
 249
 250 z70=(12v,0v);
 251 z74=(12v,4v);
 252 z76=(12v,6v);
 253
 254 z80=(14v,0v);
 255 z83=(14v,3v);
 256 z86=(14v,6v);
 257
 258 z90=(16v,0v);
 259 z92=(16v,2v);
 260 z96=(16v,6v);
 261
 262 z100=(18v,0v);
 263 z101=(18v,1v);
 264 z106=(18v,6v);
 265
 266 z110=(20v,0v);
 267 z116=(20v,6v);
 268
 269
 270 pickup pencircle scaled 0.4pt;
 271 draw(z10--z16);
 272 draw(z20--z26);
 273 draw(z30--z36);
 274 draw(z40--z46);
 275 draw(z50--z56);
 276 draw(z60--z66);
 277 draw(z70--z76);
 278 draw(z80--z86);
 279 draw(z90--z96);
 280 draw(z100--z106);
 281 draw(z110--z116);
 282 drawarrow(z15--z65);
 283 drawarrow(z24--z74);
 284 drawarrow(z33--z83);
 285 drawarrow(z42--z92);
 286 drawarrow(z51--z101);
 287
 288 label.top(btex $x_0$ etex,z16);
 289 label.top(btex $x_1$ etex,z26);
 290 label.top(btex $x_2$ etex,z36);
 291 label.top(btex \dots etex,z66);
 292 label.top(btex $x_{n-2}$ etex,z106);
 293 label.top(btex $x_{n-1}$ etex,z116);
 294
 295 endfig;
 296
 297
 298
 299 beginfig(4);
 300 v:=u*5mm;
 301
 302 z1075=(7.5v,0v);
 303
 304 z10=(0v,1v);
 305 z175=(7.5v,1v);
 306 z115=(15v,1v);
 307
 308 z20=(0v,2v);
 309 z235=(3.5v,2v);
 310 z211=(11.5v,2v);
 311 z215=(15v,2v);
 312
 313 z30=(0v,3v);
 314 z335=(3.5v,3v);
 315 z37=(7v,3v);
 316 z38=(8v,3v);
 317 z311=(11.5v,3v);
 318 z315=(15v,3v);
 319
 320 z40=(0v,4v);
 321 z415=(1.5v,4v);
 322 z455=(5.5v,4v);
 323 z47=(7v,4v);
 324 z48=(8v,4v);
 325 z495=(9.5v,4v);
 326 z413=(13.5v,4v);
 327 z416=(15v,4v);
 328
 329 z50=(0v,5v);
 330 z515=(1.5v,5v);
 331 z53=(3v,5v);
 332 z54=(4v,5v);
 333 z555=(5.5v,5v);
 334 z57=(7v,5v);
 335 z58=(8v,5v);
 336 z595=(9.5v,5v);
 337 z511=(11v,5v);
 338 z512=(12v,5v);
 339 z513=(13.5v,5v);
 340 z516=(15v,5v);
 341
 342 z60=(0v,6v);
 343 z61=(1v,6v);
 344 z62=(2v,6v);
 345 z63=(3v,6v);
 346 z64=(4v,6v);
 347 z65=(5v,6v);
 348 z66=(6v,6v);
 349 z67=(7v,6v);
 350 z68=(8v,6v);
 351 z69=(9v,6v);
 352 z610=(10v,6v);
 353 z611=(11v,6v);
 354 z612=(12v,6v);
 355 z613=(13v,6v);
 356 z614=(14v,6v);
 357 z615=(15v,6v);
 358
 359 z71=(1v,7v);
 360 z72=(2v,7v);
 361 z75=(5v,7v);
 362 z76=(6v,7v);
 363 z79=(9v,7v);
 364 z710=(10v,7v);
 365 z713=(13v,7v);
 366 z714=(14v,7v);
 367
 368
 369
 370
 371 pickup pencircle scaled 0.4pt;
 372 draw(z10--z115--z215--z20--cycle);
 373 draw(z30--z37--z47--z40--cycle);
 374 draw(z38--z315--z416--z48--cycle);
 375 draw(z50--z53--z63--z60--cycle);
 376 draw(z54--z57--z67--z64--cycle);
 377 draw(z58--z511--z611--z68--cycle);
 378 draw(z512--z516--z615--z612--cycle);
 379 drawarrow(z71--z61);
 380 drawarrow(z72--z62);
 381 drawarrow(z75--z65);
 382 drawarrow(z76--z66);
 383 drawarrow(z79--z69);
 384 drawarrow(z710--z610);
 385 drawarrow(z713--z613);
 386 drawarrow(z714--z614);
 387 drawarrow(z515--z415);
 388 drawarrow(z555--z455);
 389 drawarrow(z595--z495);
 390 drawarrow(z513--z413);
 391 drawarrow(z335--z235);
 392 drawarrow(z311--z211);
 393 drawarrow(z175--z1075);
 394
 395 endfig;
 396
 397
 398 beginfig(5);
 399 v:=u*5mm;
 400
 401 z075=(7.5v,8v);
 402
 403 z10=(0v,7v);
 404 z175=(7.5v,7v);
 405 z115=(15v,7v);
 406
 407 z20=(0v,6v);
 408 z235=(3.5v,6v);
 409 z211=(11.5v,6v);
 410 z215=(15v,6v);
 411
 412 z30=(0v,5v);
 413 z335=(3.5v,5v);
 414 z37=(7v,5v);
 415 z38=(8v,5v);
 416 z311=(11.5v,5v);
 417 z315=(15v,5v);
 418
 419 z40=(0v,4v);
 420 z415=(1.5v,4v);
 421 z455=(5.5v,4v);
 422 z47=(7v,4v);
 423 z48=(8v,4v);
 424 z495=(9.5v,4v);
 425 z413=(13.5v,4v);
 426 z416=(15v,4v);
 427
 428 z50=(0v,3v);
 429 z515=(1.5v,3v);
 430 z53=(3v,3v);
 431 z54=(4v,3v);
 432 z555=(5.5v,3v);
 433 z57=(7v,3v);
 434 z58=(8v,3v);
 435 z595=(9.5v,3v);
 436 z511=(11v,3v);
 437 z512=(12v,3v);
 438 z513=(13.5v,3v);
 439 z516=(15v,3v);
 440
 441 z60=(0v,2v);
 442 z61=(1v,2v);
 443 z62=(2v,2v);
 444 z63=(3v,2v);
 445 z64=(4v,2v);
 446 z65=(5v,2v);
 447 z66=(6v,2v);
 448 z67=(7v,2v);
 449 z68=(8v,2v);
 450 z69=(9v,2v);
 451 z610=(10v,2v);
 452 z611=(11v,2v);
 453 z612=(12v,2v);
 454 z613=(13v,2v);
 455 z614=(14v,2v);
 456 z615=(15v,2v);
 457
 458 % ve skutecnosti dle znaceni
 459 % by melo byt z6* ale uz
 460 % obsazeno
 461 z815=(1.5v,2v);
 462 z855=(5.5v,2v);
 463 z895=(9.5v,2v);
 464 z813=(13.5v,2v);
 465
 466 z715=(1.5v,1v);
 467 z755=(5.5v,1v);
 468 z795=(9.5v,1v);
 469 z713=(13.5v,1v);
 470
 471 z9=(4v,0v);
 472
 473 pickup pencircle scaled 0.4pt;
 474 draw(z10--z115--z215--z20--cycle);
 475 draw(z30--z37--z47--z40--cycle);
 476 draw(z38--z315--z416--z48--cycle);
 477 draw(z50--z53--z63--z60--cycle);
 478 draw(z54--z57--z67--z64--cycle);
 479 draw(z58--z511--z611--z68--cycle);
 480 draw(z512--z516--z615--z612--cycle);
 481 drawarrow(z075--z175);
 482 drawarrow(z415--z515);
 483 drawarrow(z455--z555);
 484 drawarrow(z495--z595);
 485 drawarrow(z413--z513);
 486 drawarrow(z235--z335);
 487 drawarrow(z211--z311);
 488 drawarrow(z815--z715);
 489 drawarrow(z855--z755);
 490 drawarrow(z895--z795);
 491 drawarrow(z813--z713);
 492
 493 label.llft(btex $n$ etex,z075);
 494 label.bot(btex $S_n$ etex,z175);
 495 label.bot(btex $S_{n\over 2}$ etex,z335);
 496 label.bot(btex $S_{n\over 2}$ etex,z311);
 497 label.bot(btex $S_{n\over 4}$ etex,z515);
 498 label.bot(btex $S_{n\over 4}$ etex,z555);
 499 label.bot(btex $S_{n\over 4}$ etex,z595);
 500 label.bot(btex $S_{n\over 4}$ etex,z513);
 501 label.rt(btex Bitonick\'a t\v r\'\i di\v cka $B_{n}$ etex,z9);
 502
 503 endfig;
 504
 505
 506
 507 beginfig(6);
 508 v:=u*5mm;
 509
 510 z1075=(7.5v,0v);
 511
 512 z10=(0v,1v);
 513 z175=(7.5v,1v);
 514 z115=(15v,1v);
 515
 516 z20=(0v,2v);
 517 z235=(3.5v,2v);
 518 z211=(11.5v,2v);
 519 z215=(15v,2v);
 520
 521 z30=(0v,3v);
 522 z335=(3.5v,3v);
 523 z37=(7v,3v);
 524 z38=(8v,3v);
 525 z311=(11.5v,3v);
 526 z315=(15v,3v);
 527
 528 z40=(0v,4v);
 529 z415=(1.5v,4v);
 530 z455=(5.5v,4v);
 531 z47=(7v,4v);
 532 z48=(8v,4v);
 533 z495=(9.5v,4v);
 534 z413=(13.5v,4v);
 535 z416=(15v,4v);
 536
 537 z50=(0v,5v);
 538 z515=(1.5v,5v);
 539 z53=(3v,5v);
 540 z54=(4v,5v);
 541 z555=(5.5v,5v);
 542 z57=(7v,5v);
 543 z58=(8v,5v);
 544 z595=(9.5v,5v);
 545 z511=(11v,5v);
 546 z512=(12v,5v);
 547 z513=(13.5v,5v);
 548 z516=(15v,5v);
 549
 550 z60=(0v,6v);
 551 z61=(1v,6v);
 552 z62=(2v,6v);
 553 z63=(3v,6v);
 554 z64=(4v,6v);
 555 z65=(5v,6v);
 556 z66=(6v,6v);
 557 z67=(7v,6v);
 558 z68=(8v,6v);
 559 z69=(9v,6v);
 560 z610=(10v,6v);
 561 z611=(11v,6v);
 562 z612=(12v,6v);
 563 z613=(13v,6v);
 564 z614=(14v,6v);
 565 z615=(15v,6v);
 566
 567 z71=(1v,7v);
 568 z72=(2v,7v);
 569 z75=(5v,7v);
 570 z76=(6v,7v);
 571 z79=(9v,7v);
 572 z710=(10v,7v);
 573 z713=(13v,7v);
 574 z714=(14v,7v);
 575
 576
 577
 578
 579 pickup pencircle scaled 0.4pt;
 580 draw(z10--z115--z215--z20--cycle);
 581 draw(z30--z37--z47--z40--cycle);
 582 draw(z38--z315--z416--z48--cycle);
 583 draw(z50--z53--z63--z60--cycle);
 584 draw(z54--z57--z67--z64--cycle);
 585 draw(z58--z511--z611--z68--cycle);
 586 draw(z512--z516--z615--z612--cycle);
 587 drawarrow(z71--z61);
 588 drawarrow(z72--z62);
 589 drawarrow(z75--z65);
 590 drawarrow(z76--z66);
 591 drawarrow(z79--z69);
 592 drawarrow(z710--z610);
 593 drawarrow(z713--z613);
 594 drawarrow(z714--z614);
 595 drawarrow(z515--z415);
 596 drawarrow(z555--z455);
 597 drawarrow(z595--z495);
 598 drawarrow(z513--z413);
 599 drawarrow(z335--z235);
 600 drawarrow(z311--z211);
 601 drawarrow(z175--z1075);
 602
 603 label.top(btex $M_8$ etex,z175);
 604 label.top(btex $M_4$ etex,z335);
 605 label.top(btex $M_4$ etex,z311);
 606 label.top(btex $M_2$ etex,z515);
 607 label.top(btex $M_2$ etex,z555);
 608 label.top(btex $M_2$ etex,z595);
 609 label.top(btex $M_2$ etex,z513);
 610
 611 endfig;
 612
 613
 614 beginfig(7);
 615 v:=u*7mm;
 616
 617 z12=(1v,2v);
 618 z13=(1v,3v);
 619 z16=(1v,6v);
 620 z356=(3.5v,6v);
 621 z40=(5v,1v);
 622 z42=(5v,2v);
 623 z47=(5v,6.5v);
 624 z72=(9v,2v);
 625 z74=(9v,4v);
 626 z76=(9v,6v);
 627
 628 z100=(0.5v,0.5v);
 629 z101=(1.5v,0.5v);
 630
 631 z0=whatever[z13,z356];
 632 z1=whatever[z356,z74];
 633 z1=z0+4v*right;
 634 z2=whatever[z12,z72];
 635 z2=z0+whatever*down;
 636 z3=whatever[z12,z72];
 637 z3=z1+whatever*down;
 638 z4=z356+4v*right;
 639 z5=whatever[z72,z76];
 640 z5=whatever[z4,z1+4v*right];
 641 z6=whatever[z40,z47];
 642 z6=z74+4v*left;
 643
 644
 645 pickup pencircle scaled 0.4pt;
 646 draw(z16--z12--z72--z76);
 647 draw(z13--z356--z74);
 648 draw(z40--z47) dashed evenly;
 649 draw(z1--z4) dashed withdots scaled 0.7;
 650 draw(z4--z5) dashed withdots scaled 0.7;
 651 draw(z0--z6) dashed withdots scaled 0.7;
 652 draw(z0--z2) dashed evenly;
 653 draw(z1--z3) dashed evenly;
 654
 655 draw(z100--z101) dashed withdots scaled 0.7;
 656
 657 pickup pencircle scaled 3pt;
 658 drawdot(z0);
 659 drawdot(z1);
 660
 661 label.bot(btex \strut 0 etex,z12);
 662 label.bot(btex $k$ etex,z2);
 663 label.llft(btex \strut ${n\over 2} - 1$ etex,z42);
 664 label.bot(btex \strut $k+{n\over 2}$ etex,z3);
 665 label.bot(btex \strut $n-1$ etex,z72);
 666 label.rt(btex posloupnost prohozen\'a separ\'atorem etex,z101);
 667
 668 endfig;
 669
 670
 671
 672
 673
 674
 675
 676 end;