Page 6 - Enterpress Magazin - 1990/1.

6. oldal ENTER PRESS 1990. szeptember

TÖMBÖK RENDEZÉSE

A számítógép - mint tudjuk - sok mindenre jó. Adatok, adatbázisok kezelésére különösen. Egy ilyen állományban sokkal gyorsab-
ban érhetünk el információkat, ha a belsejében rend van. A karbantartó munkát valamilyen rendteremtő algoritmusra kell bíznunk.
Rengeteg ilyen létezik, mi ezek közül most a beszúrásos rendezéssel (Insertion- Sort) ismerkedünk meg.
Összekevert számsort rendezünk növekvő sorrendbe. A beszúrásos módszer a következőket teszi: mozgat egy mutatót, amely
az éppen feldolgozás alatt álló adatra mutat. A mutató a második pozíciótól az utolsó felé halad. Összehasonlítja a mutatónál lévő
adatot az előtte levő, eggyel kisebb sorszámú adattal. Amennyiben a kisebb sorszámú adat értéke kisebb vagy egyenlő, mint az aktu-
ális, akkor nincs semmi tennivalója csupán a mutatót kell eggyel növelnie. Ellenkező esetben a mutatónál lévő adatot megjegyzi, és
elkezdi a mutató értékénél kisebb sorszámú adatokat egy hellyel „jobbra” eggyel nagyobb sorszámú pozícióra mozgatni, az aktuális
mutatóértéktől lefelé a kisebb sorszámok felé haladva egészen addig, amíg a megjegyzett adatnál kisebbet vagy azzal egyenlőt nem
talál. Ekkor a megüresedett helyre beírja a megjegyzett adatot, majd növeli a mutatót, és folytatja a rendezést.
A könnyebb érthetőség kedvéért nézzük a következő, félig már rendezett számsort:

Sorszám 1. 2. 3. 4. 5. 6. 7.
Adat 15 27 53 21 77 22 15

Legyen a mutató értéke éppen 4. Összehasonlítja a 21-et az 53-mal. A 21 nyilván rossz helyen van, megjegyzi a számot. Elindítja
az adatok mozgatását „jobbra” a 3. poazíciótól kezdve a csökkenő sorszámok felé, egészen addig, amíg a 21-nél kisebbet vagy azzal
egyenlőt nem talál. A mozgatás befejezésekor a 21-et beszúrja a megfelelő helyre. A módosult sor:

Sorszám 1. 2. 3. 4. 5. 6. 7.
Adat 15 21 27 53 77 22 15

Növeli a mutató értékét, így az az 5. adatra mutat. A 77 viszont nagyobb, mint az 53, tehát nincs semmilyen művelet, csak a
mutatót kell növelnie. A rendezés véget ér, ha a mutató elérte a tömbhatárt, és az utolsó mozgatás is véget ért. Az algoritmust
Basic-ben a listán látható program valósítja meg:

10 PROGRAM „INSORT.BAS” 27 END IF
11 DEF TOLT 28 NEXT
12 FOR 1=1 TO UBOUND(A) 29 END DEF
13 LET A(I)=RND(5000) 30 DEF KIIR
14 NEXT 31 FOR 1=1 TO UBOUND(A)
15 LET A(0)=-INF 32 PRINT I,A(I)
16 END DEF 33 NEXT
17 DEF REND 34 END DEF
18 FOR 1=2 TO UBOUND(A) 35 REM *** FOPROGRAM ***
19 IF A(I)<A(I-1) THEN 36 RANDOMIZE
20 LET M=A(I) 37 NUMERIC A(0 TO 20)
21 LET Z=I-1 38 CLEAR SCREEN
22 DO 39 CALL TOLT
23 LET A(Z+1)=A(Z) 40 CALL KIIR
24 LET Z=Z-1 41 CALL REND
25 LOOP UNTIL A(Z)<=M 42 CALL KIIR
26 LET A(Z+1)=M 43 END

Az „A” tömb elemeit a „TOLT” inicializálja, a „KIIR” megjeleníti, a „REND” rendezi. Természetesen a „REND” eljárás másik
programban is használható, a tömbnek új nevet, módosított hosszat is adhatunk. A legnagyobb tömbméretnek a gép memóriája és
szabad időnk nagysága szab határt. A programot 200 elemmel próbáltam ki: a futási idő 4 perc 40 másodperc volt. Valószínű, hogy
TURBO ENTERPRISE-on valamivel jobb eredmények születnének.
Ezek szerint nem elég hatékony a beszúrásos rendezés? Ebben az állapotban tényleg nem. De van megoldás: ZZZIP compiler!
A rendezés tipikus példája a ZZZIP alkalmazásának. A program simán „lefordul”, és 200 adat esetén 5 másodperc alatt lefut. Az idők
önmagukért beszélnek, a javulás közel 60-szoros!
Természetesen 200 adat nem számít nagy mennyiségnek, komolyabb alkalmazásoknál több ezerrel kell számolni Ezzel már a
fordított Basic program is nehezen birkózik meg. Hétezer adatnál negyedóra elteltével meguntam a várakozást. A rendezést úgy
gyorsíthatjuk, ha más, hatékonyabb algoritmust állítunk munkába, és igazi, compiler típusú nyelven (Pascal) írjuk meg az adatren-
dező programot.

Ezekre még visszatérünk.