Keresés és rendezés

< reláció: rendezés
(U,<) pár: rendezett halmaz ill. típus

Keresés rendezett halmazban

Def: Keresés feladata

Adott egy S $\subseteq$ (U,<) és egy s ∈ U. A feladatunk annak eldöntése, hogy s ∈ S teljesül-e.

Lineáris keresés

• Algoritmus:
  • s-et először s1-gyel hasonlítjuk, ha ez alapján nem kapunk válasz akkor s2-vel…
• Költség:
  • Legrosszabb eset: A halmaz minden elemével hasonlítunk, ez n összehasonlítást jelent.
  • Átlagos költség: A lehetséges összehasonlítások számának (n+1 db) átlaga: ${\frac {1+2+...+n-1+n+n}{n+1}}={\frac {n}{2}}+{\frac {n}{n+1}}$
• Használhatóság:
  • Ha listában, vagy külső táras állományban kell rendeznünk. (ekkor nehézkes a lista középső tagjának vizsgálata)

Bináris keresés

• Algoritmus:
  • s-et összehasonlítom S (S = {s1,s2,…,sn}) középső elemévél, si-vel.
    • ha s = si akkor végeztünk
    • ha s < si akkor {s1,…,si-1} részhalmazban keresünk
    • ha s > si akkor {si+1,…,sn} részhalmazban keresünk
• Költség:
  • Log2(n)+1 (a j-edik összehasonlítás után megmaradt Sj halmaz elemszámára fennáll: $|Sj|\leq {\frac {n}{2^{j}}}$ , j+1 lépésre van szükség, j+1=log2(n)+1 ($\lceil {log_{2}(n+1)}\rceil$))
• Használhatóság:
  • Ha S középső elemének vizsgálata nem okoz nehézséget. Pl.: S-t tömbben tároljuk.

Összehasonlítás alapú rendező módszerek

Def: Rendezés feladata

Adott egy A[1:n] tömb, melynek elemei (U,<)-ből valók. A feladat A tömb elemeit átrendezni úgy, hogy < szerint nemcsökkenő sorrendben legyenek.

Buborék-rendezés

• Algoritmus:
  • Procedure buborék

for (j=n-1, j>0, j:=j-1) do
	 for (i=1, i<=j, i:=i+1) do
		  { ha A[i+1]< A[i], akkor cseréljük ki őket. }
		  

• Költség:
  • Összehasonlítások száma: minden esetben ${\frac {n(n-1)}{2}}$.
  • Cserék száma: legrosszabb esetben (ha a tömb fordítva van kezdetben) ugyanennyi.
• Használhatóság:
  • Kis sorozatok (max 10-20 eleműek) esetén használható, egyébként sok összehas.-t igényel.
  • Konzervatív.

Beszúrásos rendezés

• Algoritmus:
  • Tegyük fel, hogy A[1 : k ] résztömb rendezett.
  • Ezt felhasználva rendezzük A[1 : k+1] résztömböt:
    • A k+1-edik elemet kell beszúrni az A[1 : k] tömbbe. Ennek során használhatunk lineáris, ill. bináris keresést.
• Költség:
  • Összehas.:
    • Lineáris kereséssel
      • Legrosszabb eset: ${\frac {n(n-1)}{2}}$ (k+1-dik. elem beszúrásakor legrosszabb esetben k öh. kell.)
      • Átlagosan: ${\frac {n(n-1)}{4}}$ (egy <a href="#_Lineáris_keresés">lineáris keresés költsége</a> > k/2, ezt kell összegezni k=1,2,…,n-1-re)
    • Bináris kereséssel (mindig ennyi)
      • $n\lceil {log_{2}(n)}\rceil$ (egy bin. keresés költsége: $\lceil {log_{2}(k+1)}\rceil$, ezt kell összegezni k=1,…,n-1 -re)
  • Cserék: (független a kereséstől)
    • Legrosszabb eset: ${\frac {(n+2)(n-1)}{2}}$
    • Átlagosan: ${\frac {n^{2}}{4}}$

• Használhatóság:
  • Túl sok mozgatást igényel.

Egy alsó becslés

• Tétel: Tegyük fel, hogy egy pusztán két kimenetelű döntéseket használó program legfeljebb k ilyen döntés alapján rendezi n elem bármelyik bemeneti sorrendjét. Ekkor k≥ $log_{2}(n!)$ teljesül.
• Köv: Egy összehasonlítás alapú rendező módszer n elem rendezésekor legalább $log_{2}(n!)$ összehaonlítást használ.
• Bizonyítás menete:
  • Tfh. van egy algoritmus, ami u_nminden permutációját (n!) rendezi és kétkimenetelű döntéseken alapul.
  • Tfh. legfeljebb k döntés elég.
  • k hosszúságú kódszó, ami minden bemenetre más.
  • A kódszavak száma 2^kamiből 2^k≥ n!

Összefésülés (MERGE)

TFH: A[1:k] és B[1:l] tömbök rendezettek és tartalmukat rendezetten akarjuk tárolni a C[1:k+l] tömbben. C[1]-be az A[1] és B[1] közül a nagyobb kerül (legyen ez most A[1]), ekkor C[2]be az A[2] és B[1]közül kerül a nagyobb. Ha ily módon MERGE-eltük pl. az A[1:x] és B[1:y] tömböket akkor elemeik nemcsökkenően a C[1:x+y]-ban vannak, és ekkor igaz, hogy C[x+y+1]:=min{A[x+1], B[y+1]}

Összefésüléses rendezés (МSORT)

• Algoritmus (rekurzív):
  • MSORT(A[1:n]) := MERGE(MSORT(A[1:$\lceil {\frac {n}{2}}\rceil$]), MSORT(A[$\lceil {\frac {n}{2}}\rceil$+1:n]))

MSORT(A[i:i]) az üres utasítás

• • ahol MERGE(összefésülés) a következő:
    • Két már rendezett sorozat egy sorozatba való rendezése.
    • Ha az A[1:i] és B[1:j] résztömböket már feldolgoztuk, akkor C[i+j+1] = min{A[i+1], B[j+1]}
    • Költség: k+l-1 összehas., k+l mozgatás (k és l A ill. B elemszáma)
• Költség:
  • Összehas.: T(n)=$n\lceil {log_{2}(n)}\rceil$ (T(n) ≤ n-1+2T(n/2) és T(1) = 0)
  • Csere: $2n\lceil {log_{2}(n)}\rceil$ (egy fázisban az összefésülés 2n mozgatással megvalósítható, $\lceil {log_{2}(n)}\rceil$ fázis van)
• Használhatóság:
  • Szükség lehet segédtömbre, vagy bonyolult módszerek alkalmazására.
  • Konstans szorzó erejéig optimális módszer.

Kupac adatszerkerezet és kupacos rendezés

• Def: A kupac adatszerkezet
  • Egy (U,<) rendezett típus, BESZÚR és MINTÖR művelettel.
  • Használhatóság: prioritási sor, összefésülés, kupacos rendezés
• Bináris kupac (a kupac adatszerkezet egy implementációja)
  • A kupac elemeit egy teljes bináris fában tároljuk. A fa csúcsaiban vannak az elemek.
  • A fára teljesül a kupac tulajdonság: egy tetszőleges csúcs eleme nem lehet nagyobb a fiaiban lévő elemeknél.
  • A teljes bináris fák jól ábrázolhatók tömbben. (A[i] bal fia A[2i], jobb fia A[2i+1])
  • Kupacépítés
    • Az f fa v csúcsaira lentről felfelé, jobbról balra felszivárog(v)
    • felszivárog(f) (a az f-ben lévő, a1,a2 f fiaiban lévő elem)
      • Ha min{a1,a2}<a, akkor min{a1,a2} helyet cserél a-val.
      • Ha az a elem ai-vel cserélt helyet, akkor felszivárog(fi).
    • felszivárog(f) költsége: l-1 csere és 2(l-1) összehas. (l a szintek száma)
  • Kupacépítés költsége:
    • cserék száma: 2n (felszivárog költsége az i-edik szinten egy csúcsra: l-i cs., egy szinten ≤2^i-1csúcs, összesen $\sum _{i=1}^{l}(l-i)2^{i-1}$ csere)
    • összehas. száma: 4n (a felszivárog során 2-szer annyi öh. kell mint csere)
  • MINTÖR megvalósítás
    • Gyökérből kivesszük az elemet, helyére tesszük a jobb alsó elemet, majd felszivárog(f)
    • Költség: O(l) = O(logn)
  • BESZÚR(s) megvalósítása:
    • Új levelet adunk a fához, és addig mozgatjuk felfelé, amíg s<s’ teljesül.
    • Költség: O(l) = O(logn)
• Kupacos rendezés
  • Algoritmus:
    • n elemből kupacot építünk
    • n darab MINTÖR megadja nem csökkenő sorrendben az elemeket.
  • Költség: O(n)+O(nlogn)
  • Összesített költsége a felső becslések alapján a rendező eljárások között a legjobb.
• A d-kupacok
  • A bináris kupacok általánosításai. Egy csúcsnak d fia lehet. Minden jellemzője a bináris eljárások általánosításával kapható meg.

Gyorsrendezés

• Algoritmus: GYORSREND(A[1:n])
  • Válasszunk egy véletlen s elemet az A tömbből.

PARTÍCIÓ(s); az eredmény legyen az A[1:k], A[k+1:l], A[l+1:n] felbontás

GYORSREND(A[1:k]);GYORSREND(A[l+1:n])

• • PARTÍCIÓ(s)

1. 1. 1. Adott A[1:n] tömb és s elem, illetve i és j változók.
      2. i-t 1-től indítva növeljük, amíg A[i]<s teljesül. Utána j-t n-től indítva csökkentjük, amíg A[j]≥s.
      3. Ha mindkettő megáll és i<j, akkor felcseréljük A[i]-t és A[j]-t. i:=i+1; j:=j-1.
      4. Ha i<j már nem áll fenn, akkor s előfordulásait a felső rész elejére mozgatjuk.

• • • A PARTÍCÍÓ költsége: O(n)
• Költség: 1.39nlogn+O(n)
  • (C(n,j), ha j szerint partícionálunk. C(n,j)=n-1+C(j-1)+C(n-j) Minden j ugyanakkora eséllyel indul: $C(n)={\frac {1}{n}}\sum _{i=1}^{n}C(n,i)$, ebbe behelyettesítjük az előzőt, majd C(n-1)-re is felírjuk, a kettőt egymásból kivonjuk, átalakítunk, becslünk)
• Használhatóság:
  • Átlagos költsége a legjobb.

A k-adik elem kiválasztása

• A max (min) elem kiválasztása
  • Költség: n-1 (pl buborék rendezéssel, de ennyi mindenképpen kell is: ahhoz, hogy u-ról belássuk, hogy max. minden más elemre szükség van egy olyan összehas-ra, amiben alulmarad u-val szemben)
• k-adik elem
  • Rendezzük az n elemet O(nlogn) lépésben, majd kiválasztjuk a k-adik elemet. Ez O(nlogn) lépés.
  • O(n) lépésszámmal:
    • Ha (k≤n/logn) vagy k≥(n-n/logn): építsünk kupacot, majd hajtsunk végre k MINTÖR-t.
    • Általánosan: bonyolult algoritmusok, amik csak nagy n esetén veszik fel a versenyt a fenti megoldásokkal. (redukciós módszer, polgár keresése)

Kulcsmanipulációs rendezések

• A kulcsok belső szerkezetéről szóló ismereteket is kihasználjuk.

Ládarendezés

• A[1:n] tömböt kell rendezni, ahol az elemek m-félék lehetnek.
• Algoritmus:
  • Létrehozunk egy U elemeivel indexelt B tömböt (m hosszú).
  • Végigolvassuk A tömböt és az s=A[i] elemet a B[s] lista végére fűzzük.
  • Növekvő sorrendben végigmegy B-n és a B[i] listák tartalmát visszaírjuk A-ba.
• Költség: O(n+m), tehát ha m≤cn, akkor O(n)
• Használhatóság:
  • A módszer akkor hasznos, ha a lehetséges elemtípusok száma nem túl nagy a rendezendő elemek számához képest.

Radix rendezés

• Használhatóság:
  • A rendezendő kulcsok összetettek és a < reláció a komponensek rendezéséből álló lexikografikus rendezés. Pl: t1,…,tk és u1,…,uk két kulcs U-ból. t1,…,tk > u1,…,uk, ha teljesül, hogy ti>ui a legkisebb i indexre, amelyre ti ≠ ui.
• Algoritmus:
  • Rendezzük a sorozatot az utolsó, k-adik komponensek szerint ládarendezéssel.
  • Az eredményül kapott sorozatot ládarendezzük k-1-edik komponens szerint, …, végül az első komponens szerint.
• Annak bizonyítása, hogy az algoritmus jó eredményt ad:
  • k=2 esetben: X=x1x2; Y=y1y2; Ha X < Y akkor
    • vagy x1<y1, ekkor a 2. rendezés biztosítja a helyes sorrendet.
    • vagy (x1=x2) & (x2<y2), ekkor az 1. rendezés után X megelőzi Y-t és ez a sorrend a 2. keresés során nem változhat.
  • Ezt könnyen általánosíthatjuk.
• Költség: $O(kn+\sum _{i=1}^{k}s_{i})$ (k db ládarendezés költségének összege(si az i-edik típus elemszáma))

Batcher-féle páros-páratlan összefésülés

Algoritmus

• Az összefésüléses rendezés során használt MERGE eljárást cseréljük le PM eljárásra.
• PM eljárás:
  • a1<…<al és b1<…<bm sorozatokat akarjuk összefésüni c1<…<cl+m sorozattá.
  • Párhuzamosan összefésüljük a1<a3<a5<… és b2<b4… sorozatot az u1<u2<u3 sorozattá, illetve az a2<a4<… és b1<b3<… sorozatot v1<v2<v3… sorozattá.
  • {ui} és {vj} párhuzamosan egyetlen lépésben összefésülhető:
    • c2i-1=min{ui,vi}, c2i=max{ui,vi} (biz:TK 50)
• A rendező algoritmus:
  • MSORT(A[1:n]) := PM(MSORT(A[1: $\lceil {\frac {n}{2}}\rceil$ ]), MSORT(A[$\lceil {\frac {n}{2}}\rceil$+1:n]))

Költség

• A PM eljárás költsége: ai és bj sorozatok öszhossza n és van $\lfloor {\frac {n}{2}}\rfloor$ processzorunk.
  • Tp(n)≤ $\lceil {log_{2}n}\rceil$ (Tp(n) ≤ Tp($\lceil {\frac {n}{2}}\rceil$)+1 (két félmeretű részfeladat párhuzamosan + {ui} és {vj} összefésülése))
• A rendezés költsége: tp(n)=O(log²n) (biz: tp(n) ≤ tp($\lceil {\frac {n}{2}}\rceil$)+$\lfloor {\frac {n}{2}}\rfloor$ )

Külső tárak tartalmának rendezése

• Cél: a lapelérések számának minimalizálása.

Összefésüléses rendezés külső tárakon

• Az eddigiek közül ez az egyetlen, ami külső tárakon is hatékony.
• Algoritmus:
  • k hosszú futam: k szomszédos lapból álló rész, amiben a rekordok rendezetten helyezkednek el.
  • k-hosszú (legroszabb esetben k=1) kezdőfutamokat hozunk létre és egyenletesen kiírjuk őket A és B állományba.
  • Összefésüljük A és B k hosszú futamait 2k hosszúvá ezeket kiírjuk C-be és D-be
  • Ezt ismételjük, amíg kész nem vagyunk.
• Költség(lapelérések száma): 2n($\lfloor {\frac {n}{2}}\rfloor$+1) (biz: $\lfloor {\frac {n}{2}}\rfloor$ menet szükséges, egy menethez 2n lapelérés tartozik)
• Gyorsítási lehetőségek:
  • Minél nagyobb kezdőfutam létrehozása.
    • Kezdeti futam létrehozása kupaccal
  • m-felé fésülés.

-- SoTi - 2005.05.23.

Használj Firefoxot, nekem sem jelenítette meg i-explorer, megkérdeztem ismerőst és mondta, hogy semmi baj az oldallal.Valóban így van. -- ati - 2007.01.02.

Hát mit ad isten, firefox-ot használok :) és most már kész a latexba fordítódás -- Tommey - 2007.01.02.