5.8. Külső rendezés

A korábbi rendezéseknél feltettük, hogy az adatok a számítógépek belső memóriájában találhatóak, s az adatok összehasonlításának, mozgatásának ideje hasonló. Ha viszont a rendezendő adatok nem férnek el egyszerre a belső memóriában, az adatok elérése, mozgatása nagyságrendekkel tovább tart az egyszerű összehasonlításoknál, és a korábban ismertetett rendezési módszerek nagyon rossz eredményeket adnak. A külső tárakon tárolt adatok elérésének gyorsítására már évtizedek óta azt a módszert használjuk, hogy nem egyesével olvassuk be az adatokat, hanem egyszerre egy lapnyi/blokknyi információt olvasunk be. Ezért a következőkben azt vizsgáljuk, hogy az adatok rendezése hány újraolvassal oldható meg.

Az összefésülő rendezésre hasonlító külső összefésülést gyakran használták korábban. Itt az eredeti állományból a belső memóriát megtöltő részeket másoltak át, azt ott helyben rendezték, ezzel úgynevezett futamokat hoztak létre, s a futamokat felváltva két állományba írták ki. Ezután a két állomány összefésülték, s ezzel a dupla hosszú futamokat hoztak létre, amit szintén két állományba írtak ki. Ezt folytatták mindaddig, amig végül egy futam maradt, ami tartalmazott minden adatot. Könnyen belátható, hogy a fázisok száma logaritmikusan függ a kezdeti futamok számától. Ezért érdemes minél hosszabb kezdő futamokkal dolgozni, (Természetesen nemcsak két input és output állománnyal lehet dolgozni, hanem többel is. Az állományok számát a hardver lehetőségei korlátozzák. A több állomány használata lecsökkenti a menetek számát.)

5.5. példa - 8. példa

Az A állomány tartalmazzon 5000 rekordot, a memóriába pedig csak 1000 rekord férjen! A kezdeti 1000 rekord hosszúságú futamok elkészítése után a szalagok a következőeket tartalmazzák:

– A (input): üres

– B (output): R1-R1000,R2001-R3000,R4001-R5000

– C (output): R1001-R2000,R3001-R4000

– D: üres

A B és C állományok összefésülésével 2000 hosszú futamok készülnek.

– A (output): R1-R2000,R4001-R5000

– B (input): üres

– C (input): üres

– D (output): R2001-R4000

Újabb összefésüléssel elkészülnének a 4000 rekord hosszúságú futamok.

– A (input): üres

– B (output): R1-R4000

– C (output): R4001-R5000

– D (input): üres

Már csak egy összefésülés van hátra.

– A (output): R1-R5000

– B (input): üres

– C (input): üres

– D: üres

S az A állományban rendezve szerepel az összes elem