5-addsort/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 drawarrow(z15--z65);
 282 drawarrow(z24--z74);
 283 drawarrow(z33--z83);
 284 drawarrow(z42--z92);
 285 drawarrow(z51--z101);
 286
 287 label.top(btex $x_0$ etex,z16);
 288 label.top(btex $x_1$ etex,z26);
 289 label.top(btex $x_2$ etex,z36);
 290 label.top(btex \dots etex,z66);
 291 label.top(btex $x_{n-2}$ etex,z96);
 292 label.top(btex $x_{n-1}$ etex,z106);
 293
 294 endfig;
 295
 296
 297
 298 beginfig(4);
 299 v:=u*5mm;
 300
 301 z1075=(7.5v,0v);
 302
 303 z10=(0v,1v);
 304 z175=(7.5v,1v);
 305 z115=(15v,1v);
 306
 307 z20=(0v,2v);
 308 z235=(3.5v,2v);
 309 z211=(11.5v,2v);
 310 z215=(15v,2v);
 311
 312 z30=(0v,3v);
 313 z335=(3.5v,3v);
 314 z37=(7v,3v);
 315 z38=(8v,3v);
 316 z311=(11.5v,3v);
 317 z315=(15v,3v);
 318
 319 z40=(0v,4v);
 320 z415=(1.5v,4v);
 321 z455=(5.5v,4v);
 322 z47=(7v,4v);
 323 z48=(8v,4v);
 324 z495=(9.5v,4v);
 325 z413=(13.5v,4v);
 326 z416=(15v,4v);
 327
 328 z50=(0v,5v);
 329 z515=(1.5v,5v);
 330 z53=(3v,5v);
 331 z54=(4v,5v);
 332 z555=(5.5v,5v);
 333 z57=(7v,5v);
 334 z58=(8v,5v);
 335 z595=(9.5v,5v);
 336 z511=(11v,5v);
 337 z512=(12v,5v);
 338 z513=(13.5v,5v);
 339 z516=(15v,5v);
 340
 341 z60=(0v,6v);
 342 z61=(1v,6v);
 343 z62=(2v,6v);
 344 z63=(3v,6v);
 345 z64=(4v,6v);
 346 z65=(5v,6v);
 347 z66=(6v,6v);
 348 z67=(7v,6v);
 349 z68=(8v,6v);
 350 z69=(9v,6v);
 351 z610=(10v,6v);
 352 z611=(11v,6v);
 353 z612=(12v,6v);
 354 z613=(13v,6v);
 355 z614=(14v,6v);
 356 z615=(15v,6v);
 357
 358 z71=(1v,7v);
 359 z72=(2v,7v);
 360 z75=(5v,7v);
 361 z76=(6v,7v);
 362 z79=(9v,7v);
 363 z710=(10v,7v);
 364 z713=(13v,7v);
 365 z714=(14v,7v);
 366
 367
 368
 369
 370 pickup pencircle scaled 0.4pt;
 371 draw(z10--z115--z215--z20--cycle);
 372 draw(z30--z37--z47--z40--cycle);
 373 draw(z38--z315--z416--z48--cycle);
 374 draw(z50--z53--z63--z60--cycle);
 375 draw(z54--z57--z67--z64--cycle);
 376 draw(z58--z511--z611--z68--cycle);
 377 draw(z512--z516--z615--z612--cycle);
 378 drawarrow(z71--z61);
 379 drawarrow(z72--z62);
 380 drawarrow(z75--z65);
 381 drawarrow(z76--z66);
 382 drawarrow(z79--z69);
 383 drawarrow(z710--z610);
 384 drawarrow(z713--z613);
 385 drawarrow(z714--z614);
 386 drawarrow(z515--z415);
 387 drawarrow(z555--z455);
 388 drawarrow(z595--z495);
 389 drawarrow(z513--z413);
 390 drawarrow(z335--z235);
 391 drawarrow(z311--z211);
 392 drawarrow(z175--z1075);
 393
 394 endfig;
 395
 396
 397 beginfig(5);
 398 v:=u*5mm;
 399
 400 z075=(7.5v,8v);
 401
 402 z10=(0v,7v);
 403 z175=(7.5v,7v);
 404 z115=(15v,7v);
 405
 406 z20=(0v,6v);
 407 z235=(3.5v,6v);
 408 z211=(11.5v,6v);
 409 z215=(15v,6v);
 410
 411 z30=(0v,5v);
 412 z335=(3.5v,5v);
 413 z37=(7v,5v);
 414 z38=(8v,5v);
 415 z311=(11.5v,5v);
 416 z315=(15v,5v);
 417
 418 z40=(0v,4v);
 419 z415=(1.5v,4v);
 420 z455=(5.5v,4v);
 421 z47=(7v,4v);
 422 z48=(8v,4v);
 423 z495=(9.5v,4v);
 424 z413=(13.5v,4v);
 425 z416=(15v,4v);
 426
 427 z50=(0v,3v);
 428 z515=(1.5v,3v);
 429 z53=(3v,3v);
 430 z54=(4v,3v);
 431 z555=(5.5v,3v);
 432 z57=(7v,3v);
 433 z58=(8v,3v);
 434 z595=(9.5v,3v);
 435 z511=(11v,3v);
 436 z512=(12v,3v);
 437 z513=(13.5v,3v);
 438 z516=(15v,3v);
 439
 440 z60=(0v,2v);
 441 z61=(1v,2v);
 442 z62=(2v,2v);
 443 z63=(3v,2v);
 444 z64=(4v,2v);
 445 z65=(5v,2v);
 446 z66=(6v,2v);
 447 z67=(7v,2v);
 448 z68=(8v,2v);
 449 z69=(9v,2v);
 450 z610=(10v,2v);
 451 z611=(11v,2v);
 452 z612=(12v,2v);
 453 z613=(13v,2v);
 454 z614=(14v,2v);
 455 z615=(15v,2v);
 456
 457 % ve skutecnosti dle znaceni
 458 % by melo byt z6* ale uz
 459 % obsazeno
 460 z815=(1.5v,2v);
 461 z855=(5.5v,2v);
 462 z895=(9.5v,2v);
 463 z813=(13.5v,2v);
 464
 465 z715=(1.5v,1v);
 466 z755=(5.5v,1v);
 467 z795=(9.5v,1v);
 468 z713=(13.5v,1v);
 469
 470 z9=(4v,0v);
 471
 472 pickup pencircle scaled 0.4pt;
 473 draw(z10--z115--z215--z20--cycle);
 474 draw(z30--z37--z47--z40--cycle);
 475 draw(z38--z315--z416--z48--cycle);
 476 draw(z50--z53--z63--z60--cycle);
 477 draw(z54--z57--z67--z64--cycle);
 478 draw(z58--z511--z611--z68--cycle);
 479 draw(z512--z516--z615--z612--cycle);
 480 drawarrow(z075--z175);
 481 drawarrow(z415--z515);
 482 drawarrow(z455--z555);
 483 drawarrow(z495--z595);
 484 drawarrow(z413--z513);
 485 drawarrow(z235--z335);
 486 drawarrow(z211--z311);
 487 drawarrow(z815--z715);
 488 drawarrow(z855--z755);
 489 drawarrow(z895--z795);
 490 drawarrow(z813--z713);
 491
 492 label.llft(btex $n$ etex,z075);
 493 label.bot(btex $S_n$ etex,z175);
 494 label.bot(btex $S_{n\over 2}$ etex,z335);
 495 label.bot(btex $S_{n\over 2}$ etex,z311);
 496 label.bot(btex $S_{n\over 4}$ etex,z515);
 497 label.bot(btex $S_{n\over 4}$ etex,z555);
 498 label.bot(btex $S_{n\over 4}$ etex,z595);
 499 label.bot(btex $S_{n\over 4}$ etex,z513);
 500 label.rt(btex Bitonick\'a t\v r\'\i di\v cka $B_{n}$ etex,z9);
 501
 502 endfig;
 503
 504
 505
 506 beginfig(6);
 507 v:=u*5mm;
 508
 509 z1075=(7.5v,0v);
 510
 511 z10=(0v,1v);
 512 z175=(7.5v,1v);
 513 z115=(15v,1v);
 514
 515 z20=(0v,2v);
 516 z235=(3.5v,2v);
 517 z211=(11.5v,2v);
 518 z215=(15v,2v);
 519
 520 z30=(0v,3v);
 521 z335=(3.5v,3v);
 522 z37=(7v,3v);
 523 z38=(8v,3v);
 524 z311=(11.5v,3v);
 525 z315=(15v,3v);
 526
 527 z40=(0v,4v);
 528 z415=(1.5v,4v);
 529 z455=(5.5v,4v);
 530 z47=(7v,4v);
 531 z48=(8v,4v);
 532 z495=(9.5v,4v);
 533 z413=(13.5v,4v);
 534 z416=(15v,4v);
 535
 536 z50=(0v,5v);
 537 z515=(1.5v,5v);
 538 z53=(3v,5v);
 539 z54=(4v,5v);
 540 z555=(5.5v,5v);
 541 z57=(7v,5v);
 542 z58=(8v,5v);
 543 z595=(9.5v,5v);
 544 z511=(11v,5v);
 545 z512=(12v,5v);
 546 z513=(13.5v,5v);
 547 z516=(15v,5v);
 548
 549 z60=(0v,6v);
 550 z61=(1v,6v);
 551 z62=(2v,6v);
 552 z63=(3v,6v);
 553 z64=(4v,6v);
 554 z65=(5v,6v);
 555 z66=(6v,6v);
 556 z67=(7v,6v);
 557 z68=(8v,6v);
 558 z69=(9v,6v);
 559 z610=(10v,6v);
 560 z611=(11v,6v);
 561 z612=(12v,6v);
 562 z613=(13v,6v);
 563 z614=(14v,6v);
 564 z615=(15v,6v);
 565
 566 z71=(1v,7v);
 567 z72=(2v,7v);
 568 z75=(5v,7v);
 569 z76=(6v,7v);
 570 z79=(9v,7v);
 571 z710=(10v,7v);
 572 z713=(13v,7v);
 573 z714=(14v,7v);
 574
 575
 576
 577
 578 pickup pencircle scaled 0.4pt;
 579 draw(z10--z115--z215--z20--cycle);
 580 draw(z30--z37--z47--z40--cycle);
 581 draw(z38--z315--z416--z48--cycle);
 582 draw(z50--z53--z63--z60--cycle);
 583 draw(z54--z57--z67--z64--cycle);
 584 draw(z58--z511--z611--z68--cycle);
 585 draw(z512--z516--z615--z612--cycle);
 586 drawarrow(z71--z61);
 587 drawarrow(z72--z62);
 588 drawarrow(z75--z65);
 589 drawarrow(z76--z66);
 590 drawarrow(z79--z69);
 591 drawarrow(z710--z610);
 592 drawarrow(z713--z613);
 593 drawarrow(z714--z614);
 594 drawarrow(z515--z415);
 595 drawarrow(z555--z455);
 596 drawarrow(z595--z495);
 597 drawarrow(z513--z413);
 598 drawarrow(z335--z235);
 599 drawarrow(z311--z211);
 600 drawarrow(z175--z1075);
 601
 602 label.top(btex $M_8$ etex,z175);
 603 label.top(btex $M_4$ etex,z335);
 604 label.top(btex $M_4$ etex,z311);
 605 label.top(btex $M_2$ etex,z515);
 606 label.top(btex $M_2$ etex,z555);
 607 label.top(btex $M_2$ etex,z595);
 608 label.top(btex $M_2$ etex,z513);
 609
 610 endfig;
 611
 612
 613 beginfig(7);
 614 v:=u*7mm;
 615
 616 z12=(1v,2v);
 617 z13=(1v,3v);
 618 z16=(1v,6v);
 619 z356=(3.5v,6v);
 620 z40=(5v,1v);
 621 z42=(5v,2v);
 622 z47=(5v,6.5v);
 623 z72=(9v,2v);
 624 z74=(9v,4v);
 625 z76=(9v,6v);
 626
 627 z100=(0.5v,0.5v);
 628 z101=(1.5v,0.5v);
 629
 630 z0=whatever[z13,z356];
 631 z1=whatever[z356,z74];
 632 z1=z0+4v*right;
 633 z2=whatever[z12,z72];
 634 z2=z0+whatever*down;
 635 z3=whatever[z12,z72];
 636 z3=z1+whatever*down;
 637 z4=z356+4v*right;
 638 z5=whatever[z72,z76];
 639 z5=whatever[z4,z1+4v*right];
 640 z6=whatever[z40,z47];
 641 z6=z74+4v*left;
 642
 643
 644 pickup pencircle scaled 0.4pt;
 645 draw(z16--z12--z72--z76);
 646 draw(z13--z356--z74);
 647 draw(z40--z47) dashed evenly;
 648 draw(z1--z4) dashed withdots scaled 0.7;
 649 draw(z4--z5) dashed withdots scaled 0.7;
 650 draw(z0--z6) dashed withdots scaled 0.7;
 651 draw(z0--z2) dashed evenly;
 652 draw(z1--z3) dashed evenly;
 653
 654 draw(z100--z101) dashed withdots scaled 0.7;
 655
 656 pickup pencircle scaled 3pt;
 657 drawdot(z0);
 658 drawdot(z1);
 659
 660 label.bot(btex \strut 0 etex,z12);
 661 label.bot(btex $k$ etex,z2);
 662 label.llft(btex \strut ${n\over 2} - 1$ etex,z42);
 663 label.bot(btex \strut $k+{n\over 2}$ etex,z3);
 664 label.bot(btex \strut $n-1$ etex,z72);
 665 label.rt(btex posloupnost prohozen\'a separ\'atorem etex,z101);
 666
 667 endfig;
 668
 669
 670
 671
 672
 673
 674
 675 end;