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