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
 459 pickup pencircle scaled 0.4pt;
 460 draw(z10--z115--z215--z20--cycle);
 461 draw(z30--z37--z47--z40--cycle);
 462 draw(z38--z315--z416--z48--cycle);
 463 draw(z50--z53--z63--z60--cycle);
 464 draw(z54--z57--z67--z64--cycle);
 465 draw(z58--z511--z611--z68--cycle);
 466 draw(z512--z516--z615--z612--cycle);
 467 drawarrow(z075--z175);
 468 drawarrow(z415--z515);
 469 drawarrow(z455--z555);
 470 drawarrow(z495--z595);
 471 drawarrow(z413--z513);
 472 drawarrow(z235--z335);
 473 drawarrow(z211--z311);
 474
 475 label.llft(btex $n$ etex,z075);
 476 label.bot(btex $S_n$ etex,z175);
 477 label.bot(btex $S_{n\over 2}$ etex,z335);
 478 label.bot(btex $S_{n\over 2}$ etex,z311);
 479 label.bot(btex $S_{n\over 4}$ etex,z515);
 480 label.bot(btex $S_{n\over 4}$ etex,z555);
 481 label.bot(btex $S_{n\over 4}$ etex,z595);
 482 label.bot(btex $S_{n\over 4}$ etex,z513);
 483
 484 endfig;
 485
 486
 487
 488 beginfig(6);
 489 v:=u*5mm;
 490
 491 z1075=(7.5v,0v);
 492
 493 z10=(0v,1v);
 494 z175=(7.5v,1v);
 495 z115=(15v,1v);
 496
 497 z20=(0v,2v);
 498 z235=(3.5v,2v);
 499 z211=(11.5v,2v);
 500 z215=(15v,2v);
 501
 502 z30=(0v,3v);
 503 z335=(3.5v,3v);
 504 z37=(7v,3v);
 505 z38=(8v,3v);
 506 z311=(11.5v,3v);
 507 z315=(15v,3v);
 508
 509 z40=(0v,4v);
 510 z415=(1.5v,4v);
 511 z455=(5.5v,4v);
 512 z47=(7v,4v);
 513 z48=(8v,4v);
 514 z495=(9.5v,4v);
 515 z413=(13.5v,4v);
 516 z416=(15v,4v);
 517
 518 z50=(0v,5v);
 519 z515=(1.5v,5v);
 520 z53=(3v,5v);
 521 z54=(4v,5v);
 522 z555=(5.5v,5v);
 523 z57=(7v,5v);
 524 z58=(8v,5v);
 525 z595=(9.5v,5v);
 526 z511=(11v,5v);
 527 z512=(12v,5v);
 528 z513=(13.5v,5v);
 529 z516=(15v,5v);
 530
 531 z60=(0v,6v);
 532 z61=(1v,6v);
 533 z62=(2v,6v);
 534 z63=(3v,6v);
 535 z64=(4v,6v);
 536 z65=(5v,6v);
 537 z66=(6v,6v);
 538 z67=(7v,6v);
 539 z68=(8v,6v);
 540 z69=(9v,6v);
 541 z610=(10v,6v);
 542 z611=(11v,6v);
 543 z612=(12v,6v);
 544 z613=(13v,6v);
 545 z614=(14v,6v);
 546 z615=(15v,6v);
 547
 548 z71=(1v,7v);
 549 z72=(2v,7v);
 550 z75=(5v,7v);
 551 z76=(6v,7v);
 552 z79=(9v,7v);
 553 z710=(10v,7v);
 554 z713=(13v,7v);
 555 z714=(14v,7v);
 556
 557
 558
 559
 560 pickup pencircle scaled 0.4pt;
 561 draw(z10--z115--z215--z20--cycle);
 562 draw(z30--z37--z47--z40--cycle);
 563 draw(z38--z315--z416--z48--cycle);
 564 draw(z50--z53--z63--z60--cycle);
 565 draw(z54--z57--z67--z64--cycle);
 566 draw(z58--z511--z611--z68--cycle);
 567 draw(z512--z516--z615--z612--cycle);
 568 drawarrow(z71--z61);
 569 drawarrow(z72--z62);
 570 drawarrow(z75--z65);
 571 drawarrow(z76--z66);
 572 drawarrow(z79--z69);
 573 drawarrow(z710--z610);
 574 drawarrow(z713--z613);
 575 drawarrow(z714--z614);
 576 drawarrow(z515--z415);
 577 drawarrow(z555--z455);
 578 drawarrow(z595--z495);
 579 drawarrow(z513--z413);
 580 drawarrow(z335--z235);
 581 drawarrow(z311--z211);
 582 drawarrow(z175--z1075);
 583
 584 label.top(btex $M_8$ etex,z175);
 585 label.top(btex $M_4$ etex,z335);
 586 label.top(btex $M_4$ etex,z311);
 587 label.top(btex $M_2$ etex,z515);
 588 label.top(btex $M_2$ etex,z555);
 589 label.top(btex $M_2$ etex,z595);
 590 label.top(btex $M_2$ etex,z513);
 591
 592 endfig;
 593
 594
 595 beginfig(7);
 596 v:=u*7mm;
 597
 598 z12=(1v,2v);
 599 z13=(1v,3v);
 600 z16=(1v,6v);
 601 z356=(3.5v,6v);
 602 z40=(5v,1v);
 603 z42=(5v,2v);
 604 z47=(5v,6.5v);
 605 z72=(9v,2v);
 606 z74=(9v,4v);
 607 z76=(9v,6v);
 608
 609 z100=(0.5v,0.5v);
 610 z101=(1.5v,0.5v);
 611
 612 z0=whatever[z13,z356];
 613 z1=whatever[z356,z74];
 614 z1=z0+4v*right;
 615 z2=whatever[z12,z72];
 616 z2=z0+whatever*down;
 617 z3=whatever[z12,z72];
 618 z3=z1+whatever*down;
 619 z4=z356+4v*right;
 620 z5=whatever[z72,z76];
 621 z5=whatever[z4,z1+4v*right];
 622 z6=whatever[z40,z47];
 623 z6=z74+4v*left;
 624
 625
 626 pickup pencircle scaled 0.4pt;
 627 draw(z16--z12--z72--z76);
 628 draw(z13--z356--z74);
 629 draw(z40--z47) dashed evenly;
 630 draw(z1--z4) dashed withdots scaled 0.7;
 631 draw(z4--z5) dashed withdots scaled 0.7;
 632 draw(z0--z6) dashed withdots scaled 0.7;
 633 draw(z0--z2) dashed evenly;
 634 draw(z1--z3) dashed evenly;
 635
 636 draw(z100--z101) dashed withdots scaled 0.7;
 637
 638 pickup pencircle scaled 3pt;
 639 drawdot(z0);
 640 drawdot(z1);
 641
 642 label.bot(btex \strut 0 etex,z12);
 643 label.bot(btex $k$ etex,z2);
 644 label.llft(btex \strut ${n\over 2} - 1$ etex,z42);
 645 label.bot(btex \strut $k+{n\over 2}$ etex,z3);
 646 label.bot(btex \strut $n-1$ etex,z72);
 647 label.rt(btex posloupnost prohozen\'a separ\'atorem etex,z101);
 648
 649 endfig;
 650
 651
 652
 653
 654
 655
 656
 657 end;