[GS]External Mergesort

[Phil]

Hellow,

een probleem bij mergesort:

we hebben een reeks records die we moete sortere met searchkeys

14, 3, 26, 13, 8, 15, 23, 1, 7, 12, 5, 4, 19, 30, 11, 6

We gaan per 2 mergen...

Dan krijgen we:
3/14 13/26 8/15,23/1, 7/12, 4/5 19/30, 6/11

in1, in 2-->
3/13 14/26 1/8 15/23 4/5 7/12 6/11 19/30

in1, in5-->
3/4 5/13 7/12 14/26 1/6 8/11 15/19 23/30

hoe zit het nu verder? btw, dit is oefening van reeks8 dus hopelijk kan iemand het uitleggen!

MERCI E

[Robbe]

gewoon verderdoen zoals je bezig was, maar ik denk dat je notatie je verwart heeft.

even een voorbeeldje van hoe ik het zou doen, alles tussen opeenvolgende '(' en ')' is een blok.

Code: Select all

--1

(14) ( 3) (26) (13) ( 8) (15) (23) ( 1) ( 7) (12) ( 5) ( 4) (19) (30) (11) ( 6)



--2

( 3   14) (13   26) ( 8   15) ( 1   23) ( 7   12) ( 4    5) (19   30) ( 6   11)



--4

( 3   13   14   26) ( 1    8   15   23) ( 4    5    7   12) ( 6   11   19   30)



--8

( 1    3    8   13   14   15   23   26) ( 4    5    6    7   11   12   19   30)



--16

( 1    3    4    5    6    7    8   11   12   13   14   15   19   23   26   30)

ik heb dus de 2 blokken 'boven' het nieuwe blok gemerged.

[pietje puk]

euhm, is da egt wel het antwoord op vraag 1, reeks 8 ??
tis namelijk ni mogelijk om meer dan 2 datarecords (getallekes dus) in een blok te steken.

dus, zoal de flip et deed (had ik me hem gedaan)..

1) eerst per 2 getallekes sorteren, per 2 in een blok steken.

2) onderling, blok1 en blok2 sorteren (aangezien ge der 2 kunt inladen)

3) blok1 met blok5, blok 2 met blok 6...etc onderling sorteren sta zo erges uitgelegd.

maar dan is die rij nog ni gesorteerd
da was dus onze vraag, oe da ge da volges opgave 1 van reeks 8 verder moet doen..

[Robbe]

ok, ik snap u verwarring omtrent mijn antwoord

ff voor de duidelijkheid voor ik met mijn uitleg begin:

• Een C(onceptueel)-blok is een blok zoals in mijn antwoord, moest het dus volledig in het geheugen gaan.
• Een R(eeel)-blok het blok met een eindige omvang, jullie blok van 2 records bijvoorbeeld.

Als de grootte van u C-blok kleiner is dan die van u R-blok, kunt ge gewoon mijn eerder beschreven ding gebruiken.

Als de C-blokken groter zijn, moet ge ze beginnen opdelen in R-blokken (als ge slim zijt, zijn die een macht van 2 groot). Om te beginnen merged ge R1 van C1 met R1 van C2. Op een gegeven moment gaat een van u R'en leeg zijn, stel die van C1. Dan vervangt ge u kopie van R1 van C1 door een kopie van R2 van C1 en doet ge verder met mergen tot er weer een blok leeg is. Ge vervangt da terug en ge gaat zo verder tot een van u C-blokken leeg is. De rest van het andere moet ge er nu gewoon achter plakken en ge kunt u volgende paar C-blokken beginnen mergen.

Is deze uitleg wa duidelijker?

[Phil]

Het is niet echt duidelijker voor mij nee
zou je die oefening anders eens kunnen uitwerke? Want uw uitleg snap ik wel ongeveer, maar we zitten daar juist vast en wete ni wa te doen...

merci..

[zarry]

http://users.telenet.be/zarry/mergesort.pdf

[Robbe]

Het is niet echt duidelijker voor mij nee
zou je die oefening anders eens kunnen uitwerke? Want uw uitleg snap ik wel ongeveer, maar we zitten daar juist vast en wete ni wa te doen...

merci..

geg: 14, 3, 26, 13, 8, 15, 23, 1, 7, 12, 5, 4, 19, 30, 11, 6

elk blok van 1 is gesorteerd (duh)

mergen naar l=2 geeft:
(3/14), (13/26), (8/ 15), (1/23), (7/ 12), (4/5), (19/ 30), (6/11)

mergen naar l=4 geeft
in1 (3/14) <- (3/14)
in2 (13/26) <- (13/26)
out -> (3/13 14/26)

in1 (8/15) <- (8/15)
in2 (1/23) <- (1/23)
out -> (1/8 15/23)

mergen naar l=8
in1 (3/13) <- (3/13 14/26)
in2 (1/8 ) <- (1/8 15/23)
out -> (1/3 8*/13* 14/15 23/26)

*=hier wordt een nieuw R-blok van 2 ingelezen uit het overeenkomstige C-blok. (C = conceptueel, gesorteerd blok, R= reeel blok)

...

dit stond eigenlijk ook al in de pdf van zarry, maar hett was me niet duidelijk of dit een antwoord op de vraag was, of een verduidelijking van het probleem.

[pietje puk]

doe da ook ies me dien anderen helft? dan krijg ik:
(4 5 6 11 7 12 19 30)
die 7 sta dus ni op zen paats. of heb ik ier iets verkeerd gedaan?
zo doe ik dien anderen helft..

mergen naar l=2 geeft:
(3/14), (13/26), (8/ 15), (1/23), (7/ 12), (4/5), (19/ 30), (6/11)

mergen naar l=4 geeft (van den anderen helft)
in1 (7/12) <- (7/12)
in2 (4/5) <- (4/5)
out -> (4/5 7/12)

in1 (19/30) <- (19/30)
in2 (6/11) <- (6/11)
out -> (6/11 19/30)

mergen naar l=8
in1 (4/5) <- (4/5 7/12)
in2 (6/11) <- (6/11 19/30)
out -> (4/5 6/11 7/12 19/30)

hier sta die 7 toch nog ni goe?

[Robbe]

hier sta die 7 toch nog ni goe?

Ah nee, ge hebt bij het mergen van u C-blokken van 4 ni eerst u R-blok ververst, ge moogt pas de rest van een C-blok erachter plakken als het andere C-blok leeg is.

Gij hebt die 6/11 er gewoon achter geplakt, terwijl ge eerst de 7/12 moest inlezen en dan pas verder doen.

voor de tweede helft:

(4/5 7/12), (6/11 19/30)

mergen naar 8
in1 (4/5) <- (4/5 7/12)
in2 (6/11) <- (6/11 19/30)
out -> (4/5 [hier wordt 7/12 ingelezen in in1] 6/7 11 [hier wordt 19/30 ingelezen in in2]/12 [C1 is nu leeg, rest van in2 en C2 erachter plakken] 19/30 [C2 is leeg, stop]

[Phil]

hoho! nu snap'k et ;p

mercii

[pietje puk]

amai ja, nu snappek da wel.

kkan mij ni herrinere dak da ooit erges tege ben gekome ze ..

tzal wss wel aan mijn enthousiamsme in de les liggen :p
altijd al te enthousiast en meewerkend geweest