Keresés és rendezés

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

< 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 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:[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 ≤2^i-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. 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: [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(log²n) (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.