Tölvumál - 01.10.1986, Qupperneq 16

töluna í vektornum B. Segjum að B innihaldi n tölur
eins og fyrr og til hægðarauka gerum við ráð fyrir að
n sé 2 i veldinu k (n=2k), þar sem k er einhver
heiltala, þá getur n tekið gildin 2,4,8,16,32,64
o.s.frv.
jt,
Venjulegi algóritminn rennir i gegum allar tölur i
vektornum B og heldur sifellt utan um stærstu töluna
sem hann hefur séð. Þegar hann hefur séð allar
tölurnar i vektornum þekkir hann stærstu töluna.
S0;
FOR i:-1 TOnDO
IF Bli] > s THEH
sBlil;
Timinn sem þetta tekur er af stærðargráðunni n, þar
sem algóritminn verður að lita á allar tölurnar i B.
Litum nú á hvernig hægt væri að finna stærstu töluna
með þvi að nota margar undirtölvur. Einn möguleiki
er að byrja á þvi að bera samtímis saman tölur sem
eru hlið við hlið i B og setja stærri töluna i
hólfið, sem hefur lægri einkennistölu. Við þurfum
n/2 undirtölvur til að gera þetta. Þá höfum við
aðeins n/2 tölur eftir, sem gætu verið stærstar, svo
einungis þarf að nota n/4 undirtölvur til að bera
saman tölurnar, sem eru i hólfunum með ójafna
einkennistölu og setja aftur stærri töluna i hólfið
með lægri einkennistölu. Næst berum við saman
tölurnar i fjórða hverju hólfi. Við höldum þessu
áfram þar til við höfum aðeins eina tölu eftir. Hún
er stærsta talan í B.
Tökum sem dæmi vektorinn B=(9,4,2,7,11,5,15,8). Við
notum 4 undirtölvur, köllum þær T1,T2,T3 og T4. T1
ber saman 9 og 4, T2 ber saman 2 og 7, T3 ber saman
11 og 5 og T4 ber saman 15 og 8. Eftir þetta þrep er
B=(9,4,7,2,11,5,15,8); aðeins T2 þurfti að skipta á
tölum. í næsta þrepi þurfum við aðeins 2
undirtölvur, svo að við notum T1 og T2 aftur. T1 ber
saman 9 og 7 og T2 ber saman 11 og 15. T2 skiptir á
11 og 15 og B er nú (9,4,7,2,15,5,11,8). í siðast
þrepinu þurfum við eina undirtölvu, sem ber saman 9
og 15 og skiptir á þeim. Við vitum nú að 15 er
stærsta talan og hún situr framst i B, sem er
(15,4,7,2,9,5,11,8). Við höfum að visu ruglað röð
16