Keresés és rendezés

A VIK Wikiből
A lap korábbi változatát látod, amilyen Ferrero (vitalap | szerkesztései) 2013. január 29., 21:05-kor történt szerkesztése után volt.
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez

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

Keresés rendezett halmazban

Def: Keresés feladata

Adott egy S [math] \subseteq [/math] (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: [math] \frac{1+2+...+n-1+n+n}{n+1} = \frac{n}{2}+\frac{n}{n+1} [/math]
  • 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: [math] |Sj| \leq \frac{n}{2^j} [/math] , j+1 lépésre van szükség, j+1=log2(n)+1 ([math] \lceil{log_2(n+1)}\rceil [/math]))
  • 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 [math] \frac{n(n-1)}{2} [/math].
    • 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: [math] \frac{n(n-1)}{2} [/math] (k+1-dik. elem beszúrásakor legrosszabb esetben k öh. kell.)
        • Átlagosan: [math] \frac{n(n-1)}{4} [/math] (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)
        • [math] n\lceil{log_2(n)}\rceil [/math] (egy bin. keresés költsége: [math] \lceil{log_2(k+1)}\rceil [/math], ezt kell összegezni k=1,…,n-1 -re)
    • Cserék: (független a kereséstől)
      • Legrosszabb eset: [math] \frac{(n+2)(n-1)}{2} [/math]
      • Átlagosan: [math] \frac{n^2}{4} [/math]
  • 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≥ [math] log_2(n!) [/math] teljesül.
  • Köv: Egy összehasonlítás alapú rendező módszer n elem rendezésekor legalább [math] log_2(n!) [/math] összehaonlítást használ.
  • Bizonyítás menete:
    • Tfh. van egy algoritmus, ami unminden 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 2kamiből 2k≥ 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:[math] \lceil\frac{n}{2}\rceil [/math]]), MSORT(A[[math] \lceil\frac{n}{2}\rceil [/math]+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)=[math] n\lceil{log_2(n)}\rceil [/math] (T(n) ≤ n-1+2T(n/2) és T(1) = 0)
    • Csere: [math] 2n\lceil{log_2(n)}\rceil [/math] (egy fázisban az összefésülés 2n mozgatással megvalósítható, [math] \lceil{log_2(n)}\rceil [/math] 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 ≤2i-1csúcs, összesen [math] \sum_{i=1}^{l}(l-i)2^{i-1} [/math] 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. 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: [math] C(n)=\frac{1}{n}\sum_{i=1}^{n}C(n,i) [/math], 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: [math] O(kn+\sum_{i=1}^{k}s_i) [/math] (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: [math] \lceil\frac{n}{2}\rceil [/math] ]), MSORT(A[[math] \lceil\frac{n}{2}\rceil [/math]+1:n]))

Költség

  • A PM eljárás költsége: ai és bj sorozatok öszhossza n és van [math] \lfloor\frac{n}{2}\rfloor [/math] processzorunk.
    • Tp(n)≤ [math] \lceil{log_2n}\rceil [/math] (Tp(n) ≤ Tp([math] \lceil\frac{n}{2}\rceil [/math])+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(log2n) (biz: tp(n) ≤ tp([math] \lceil\frac{n}{2}\rceil [/math])+[math] \lfloor\frac{n}{2}\rfloor [/math] )

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([math] \lfloor\frac{n}{2}\rfloor [/math]+1) (biz: [math] \lfloor\frac{n}{2}\rfloor [/math] 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.