Algoritem za polifazno urejanje

Pri polifaznem je pomembna osnovna porazdelitev po vseh trakovih. Pri vsem skupaj imamo vedno n-1 vhodnih trakov in in 1 izhodni trak.

S štirimi trakovi mora biti število čet na trakovih takšno:

1 0 0 0
1 1 1 0
2 2 1 0
4 3 2 0
7 6 4 0
...
a1 a2 a3 a4
a1+a2 a1+a3 a1+a4 0

Sistem za računanje števila čet na vhodnih trakovih je torej a1+ai, kjer i teče od 2 do n.

Primer zlivanja:

Trak 1: 16,4,10,14,7,9,3,2 
Trak 2:                    \ 16;7,9;2
Trak 3:                    \ 4,10,14;3

Trak 1:             4,10,14,16;3,7,9
Trak 2:  16;7,9;2 /
Trak 3: 4,10,14;3 /

Trak 1: 4,10,14,16;3,7,9 \
Trak 2:                2 \
Trak 3:                    2,4,10,14,16

Trak 1:        3,7,9 \
Trak 2:                - 2,3,4,7,9,10,14,16
Trak 3: 2,4,10,14,16 /

Če manjkajo čete, do pravilne razporeditve, uporabimo navidezne čete.

Najpomembnejši zadeve, na katere je potrebno pazit:

• porazdeljevanje
• začetno zlivanje čet - najprej zlivamo navidezne čete

Vaje

1. Zaporedje 2,9,5,4,3,6,5,4,5,7,5,6,4,5,9,7 uredi s polifaznim urejanjem, ampak namesto s četami s podzaporedji.

Rešitev:

Trak 1: 
Trak 2: 
Trak 3: 
Trak 4: 2,9,5,4,3,6,5,4,5,7,5,6,4,5,9,7 

Trak 1: 2,4,6,5,7,6,9
Trak 2: 9,3,4,5,4,7
Trak 3: ,5,5,5
Trak 4:

Trak 1: 7,6,9
Trak 2: 4,7
Trak 3: 
Trak 4: 29,345,456,555

Trak 1: 9
Trak 2: 
Trak 3: 2479,34567
Trak 4: 456,555

Trak 1: 
Trak 2: 24456799
Trak 3: 34567
Trak 4: 555

Trak 1: 2344455555667799
Trak 2: 
Trak 3: 
Trak 4: 

2. Polifazno zlivanje, 7+1 trakov. Na vhodnem traku je 27 čet. Zlijejo se lahko 8. in 14., 9. in 15., 12. in 19. Kam bomo zapolnili 26. četo?

Samo rešitev:: 26. Četa pride na 6. trak. Pri postavljanju na trakove pride do zlitja 8 in 14 čete ter 12 in 19 čete, medtem ko do zlitja 9 in 15 čete ne pride.

3. Dokaz, da med zlivanjem ne more priti do združevanja dveh čet v eno (dopolnitev zapiskov iz worda).

Imamo dva trakova, na vsakem dve četi. Četa X se zaključuje z a,...:

 1. Xa|bY
 2. Zc|dW

 Pri zlivanju dobimo [x,z]r|l[y,w], pri čemer sta r in l:
 r = max(a,c)
 l = min(b,d)
 
 Če naj se četi združita, mora veljati: r <= b.
 r <= b
 => max(a,c) <= min(b,d)
 => (c <= a) & (a <= b) & (b <= d) ali
    (c <= a) & (a <= d) & (d <= b) ali
    (a <= c) & (c <= d) & (d <= b) ali
    (a <= c) & (c <= b) & (b <= d)

 Sledi torej, da bi se četi združili že pri porazdeljevanju. 
 V prvem primeru zaradi a<=b,
 drugič zaradi (a <= d) & (d <= b) => (a <= b),
 trejič zaradi (c <= d),
 in nazadnje zaradi (c <= b) & (b <= d) => (c <= d).
 

4.

Primer: uredi naslednje zaporedje s 4 trakovi (3+1): 73 21 36 42 17 84 14 59 85 13 12 25 99 11 39 88 95

Najprej porazdelimo tevila na trakove:

A|73 21 36 42 17 84 14

B|59 85 13 12 25 99

C|11 39 88 95

D|

Na traku C je najmanj čet, zato bo ta trak naslednji prazen. Uredimo tevila na A, B, C do doline 4 (dolina traku C). Zlivamo tako, da začnemo pri prvem indeksu vsake čete, ki jih zlivamo in se vsakič, ko uporabimo element, ki nanj kae kazalec, pomaknemo za indeks naprej do konca čete.

A|17 84 14

B|25 99

C|

D|11 59 73;21 39 85;13 36 88;12 42 95

Zlivamo po en element iz A, B v vsako četo v D do doline 2 (doline najkrajega traku). Trak B bo prazen.

A|14

B|

C|11 17 25 59 73;21 39 84 85 99;

D|13 36 88;12 42 95

A|

B|11 13 14 17 25 36 59 73 88

C|21 39 84 85 99

D|12 42 95

Dolina vseh nepraznih trakov je enaka (1) - začnemo zadnje zlivanje:

A|11 12 13 14 17 21 25 36 39 42 59 73 84 85 95 99

B|

C|

D|