IV. Rendezés és rendezett tömbök

Elsõ nekifutás: rendezési algoritmusok

1. feladat: adott egy N elemû T tömb (T[1..N]). Készíts algoritmust, mely megadja, hogy hány különbözõ elem van a tömbben!

Az algoritmus rendezés nélkül kevéssé elegáns. Kell venni egy elemet, megkeresni és valamiképpen kitörölni a vele egyezõeket. Ezt addig kell csinálni, amíg van elem a tömbben.

2. feladat: ugyanaz, mint az 1. feladatnál, de most a tömb rendezett.

Ez a feladat megoldható úgy, hogy a tömbön csak egyszer kell végigmenni. Most ugyanis az egyforma elemek egymás mellett, összefüggõ blokkban helyezkednek el. A program mûködése gyorsabb lesz. Ebbõl is látható, milyen hasznos, ha rendezett tömbökkel dolgozunk.

A rendezés maga is nehéz. Lehet, hogy a 2. feladat rendezéssel együtt hosszadalmasabb, mint az 1. feladat megoldása. Éppen ezért, ha egy tömböt egyszer már rendeztünk, érdemes a továbbiakban olyan mûveleteket végezni vele, melyek megtartják a rendezettségét.

A rendezés alapfeladata: adott egy T[1..N] tömb, a programnak elõ kell állítani T elemeit rendezett sorrendben (többnyire magában a T tömbben). Ebben az esetben a rendezés a memóriában történik. Nehezebb a feladat, ha egy olyan file-t kell rendezni, amely nem fér be teljes egészében a memóriába, így a fenti algoritmusok nem, vagy csak módosítva használhatók. Ha T elemei rekordok, a rendezési szempont lehet a rekordok egyik mezõje, illetve helyben kiszámított értékeket is használhatunk szempontként (pl. ha osztály, és ezen belül név szerint akarunk rendezni). Azt az adatot, ami szerint rendezünk (és késõbb, ami szerint keresünk), kulcsnak nevezzük. Mire jó a rendezés? Fõképpen arra, hogy a rendezett sorozatban könnyebben tudjunk keresni. Pl. egy 1024 elemû sorozatban akár 1024 lépésbe is telhet, amíg soros kereséssel megtalálunk egy elemet, felezéses kereséssel azonban legfeljebb 10 lépésbe.

Az alapvetõ rendezési algoritmusok (maximum-kiválasztásos, buborékos és beillesztéses) megtalálhatók a 2. Pascal füzetke A függelékében, ezeket itt nem ismétlem meg.

Nézzük meg a buborékos rendezést még egyszer:

Ciklus I:=N..2
   Ciklus J:=1..I-1
      Ha T[J]>T[J+1] akkor Csere(J,J+1)
   Ciklus vége
Ciklus vége

Ez az algoritmus még javítható. Elõfordulhat, hogy egy ponttól kezdve (J) már nem történt csere. Ez azt jelenti, hogy a tömb attól kezdve rendezett, ekkor a következõ lépésben a belsõ ciklust már csak addig kell futtatni (tehát I értéke nem egyesével, hanem gyorsabban is csökkenhet). Ez a verzió már gyorsabban mûködik a maximumkivá lasztásos rendezésnél.

3. feladat: írd meg a javított buborékos rendezést!

Nézd át még egyszer a beillesztéses rendezés algoritmusát! Mûködési elve, hogy ha a tömb egy része már rendezett, akkor hozzávesz egy új elemet, és ezt beilleszti a megfelelõ helyre. Ha újabb elemek érkeznek, a beillesztés segítségével a tömb bõvíthetõ úgy, hogy a rendezettsége megmarad (ez gyorsabb, mint új elem érkezésekor az egész tömböt újrarendezni). A beillesztéses rendezés rekurzív felfogású, és így is átírható:

Rendez(N):
   Ha N>1 akkor Rendez(N-1)
                Beilleszt(N,N-1)

4. feladat: írd meg a beillesztéses rendezés programját rekurzív változatban! (Tulajdonképpen a külsõ ciklust váltottuk ki rekurzióval. A beillesztés ugyanaz, mint az eredeti algoritmusban.)

A következõ, egyben eddig leggyorsabb módszer a szétválogatáson alapuló rendezés, mely a Quicksort nevet viseli. Elõször foglalkozzunk a szétválogatás problémájával. A módszer lényege: kiválasztunk a tömbbõl egy elemet (mondjuk az elsõt). A többi elemet szétválogatjuk úgy, hogy a tömb bal felében az illetõ elemnél kisebbek, a jobb felében pedig nagyobbak legyenek. A kiválasztott elem végül a két fél közé kerül.

5. feladat: írj eljárást a szétválogatásra! A továbbiak miatt hasznos, ha az eljárást általános formában írjuk meg, a T tömb adott részének szétválogatására: e paraméter a szétválogatandó rész elsõ, u az utolsó elemének sorszáma. k-ban adja vissza az eljárás, hogy hová került az elsõ elem. Tipp: használj egy T-vel egyezõ méretû segédtömböt a szétválogatásra, végül másold vissza T-be a tartalmát!

Procedure Szetv(e,u:integer; var k:integer)

A szétválogatásnak létezik egy olyan, nagyon gyors formája is, amikor nem használunk fel segédtömböt. Ez a következõképpen mûködik. A szétválogatandó rész elsõ elemét megjegyezzük („kivesszük a tömbbõl"), így marad egy üres hely. Jobbról indulva megkeressük az elsõ, nála kisebb elemet, és betesszük az üres helyre. Azután ettõl a ponttól jobbra indulva megkeressük az elsõ, kiválasztottnál nagyobb elemet, és betesszük az elõzõ lépésben felszabadult helyre, stb. Végül az utolsónak felszabadult helyre betesszük az eredetileg kivett elemet (ez a pozíció kerül a K változóba).

Var m:típus; {a tömb alaptípusa}
Begin
 m:=T[e]; {megjegyezzük az elsõ elemet, e szerint válogatunk}
 while e<u do begin
    while (T[u]<m) and (e<u) do u:=u-1; {jobbról keresünk kisebbet}
       if e<u then begin
          T[e]:=T[u]; {betesszük az üres helyre, most u az üres hely}
          e:=e+1;
          while (T[e]>=m) and (e<u) do e:=e+1; {balról nagyobbat}
             if e<u then begin
             T[u]:=T[e]; {betesszük az üres helyre, most e az üres hely}
             u:=u-1;
          end;
       end;
    end;
    T[e]:=m; {visszatesszük az elején kivett elemet}
    k:=e;
 End;

Most lássuk a rekurzív Quicksort algoritmust:

Rendez(E,U)
   Szétválogat(E,U,K)
   Ha E<K-1 akkor Rendez(E,K-1)
   Ha U>K+1 akkor Rendez(K+1,U)

Tehát szétválogatjuk a tömböt az elsõ eleme szerint, majd a féltömböket ismét, stb. Az eljárás Rendez(1,N)-nel indítható.

6. feladat: írd meg a Quicksort programot!

Második nekifutás: mûveletek rendezett tömbökkel

Nézd át a programozási tételek közül a felezéses (bináris) keresés algoritmusát! Az elv rekurzív megfogalmazása: megállapítjuk, hogy a tömb melyik felében van a keresett elem, majd a tömb megfelelõ szeletére ismét alkalmazzuk a keresést. Az algoritmus maga nem rekurzív (ld. 2. Pascal füzetke, A függelék).

1. feladat: írd meg a felezéses keresés programját! A program kétféle értéket adhat vissza: a keresett elem sorszámát, vagy azt, hogy nincs megoldás.

Módosított felezéses keresés: szótárprogram használatánál nem kell beírni a teljes szót, már a szókezdet beírására is megtalálja a program a keresett szót (vagy egy ahhoz közeli szót, ha nincs olyan kezdetû szó). A módosított program tehát vagy a keresett elem, vagy a rendezés szerint közvetlenül rákövetkezõ elem sorszámát adja meg. [alma barack körte répa] sorozatban „kör"-re keresve 3, „citrom"-ra keresve 3 lesz az eredmény. „zeller" esetén pl. adhat 0-t eredményül a program. Ez nem nagy változás az eredeti algoritmushoz képest, hiszen az mindenképpen behatárolja a keresett elemet, akár létezik, akár nem. A problémát megint a különleges esetek kezelése jelenti.

2. feladat: írd meg a módosított felezéses keresés programját!

A felezéses keresés ismeretében javítható a beillesztéses rendezés algoritmusa. Eredetileg az új elem helyét soros kereséssel határoztuk meg egy már rendezett tömbrészletben. Ha erre a felezéses keresést használjuk, fõleg nagy tömbök esetén sokkal gyorsabb lesz a program. Egyetlen hátránya, hogy nehéz megírni. Ezt az elvet használja fel a beillesztéses rendezés bináris fával (ld. késõbb).

Most két rendezett tömbünk van (A[1..N] és B[1..M]). Ezek elemeit kell egy harmadik (C[1..N+M]) rendezett tömbbe másolnunk. Megtehetjük, hogy egymás után bemásoljuk a két tömb elemeit, majd rendezzük C-t, de ezt a korábbiak értelmében szeretnénk elkerülni. Az összefuttatás algoritmusa így nézhet ki:

i:=1, j:=1, db:=0
Ciklus amíg i<=N és j<=M
   db:=db+1
   Ha A[i]<B[j]   akkor C[db]:=A[i], i:=i+1
               különben C[db]:=B[j], j:=j+1
Ciklus vége

Ciklus k:=i..N
   db:=db+1, C[db]:=A[k]
Ciklus vége

Ciklus k:=j..M
   db:=db+1, C[db]:=B[k]
Ciklus vége

Az elv: mindig abban a tömbben lépünk tovább, amelyikben a kisebb elem van. Így C-be rendezve kerülnek az elemek. Ha A[i]=B[j], akkor B tömbben lépünk tovább: mivel B-ben idõvel nagyobb elemet találunk, vagy B tömb végére érünk, biztosan sorra fognak kerülni A elemei is. Mivel valamelyik tömbnek elõbb érünk a végére, az utolsó két ciklus arra szolgál, hogy a másik tömbben maradó elemeket is átmásolja C-be. (A két ciklus közül csak az egyik kerül végrehajtásra, mivel i vagy j valamelyike már túllépett az illetõ tömbön.)

Rendezett tömbök jól használhatók halmazok tárolására is, mivel a halmazban az elemek sorrendje amúgy sem számít. Felezéses keresés segítségével gyorsan eldönthetõ, hogy egy elem szerepel-e a halmazban. A halmazt ábrázoló tömbben egy elem csak egyszer szerepelhet!

A két halmaz úniója megkapható az összefutattás segítségével, egy módosítással: ha a két halmazban megegyezik egy elem, annak csak egy példányban szabad bekerülnie C-be. Így C elemszáma legfeljebb N+M, de lehet kisebb is.

3. feladat: írd meg az únió halmazmûvelet algoritmusát az összefutattás módosításával! Tipp: külön kell választanod a <, > és = eseteket.

Hasonlítsd össze ezt a 2. Pascal füzetke A függelékében lévõ únió a) algoritmussal! Ez sokkal gyorsabb, mert az egyezõ elemekhez nem keresi végig a másik tömböt: ha a keresett elemnél talál egy nagyobbat, a rendezettség miatt azután már biztosan nem következik a keresett.

4. feladat: írd meg halmazokat ábrázoló tömbökre a metszet algoritmusát! Ez azt jelenti, hogy a két halmazból csak a megegyezõ elemek kerülnek be C-be. Mekkora legfeljebb C elemszáma? Tipp: az algoritmus az únió algoritmusának egyszerû módosítása.