Keresés és rendezés forrásának megtekintése

__TOC__

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

==Keresés rendezett halmazban==

===Def: Keresés feladata===

Adott egy S <math> \subseteq </math> (U,&lt;) és egy s &isin; U. A feladatunk annak eldöntése, hogy s &isin; S teljesül-e.

<div id="_Lineáris_keresés"></div>
===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&#8230;
* 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,&#8230;,sn}) középső elemévél, si-vel.
*** ha s = si akkor végeztünk
*** ha s &lt; si akkor {s1,&#8230;,si-1} részhalmazban keresünk
*** ha s &gt; si akkor {si+1,&#8230;,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,&lt;)-ből valók. A feladat A tömb elemeit átrendezni úgy, hogy &lt; szerint nemcsökkenő sorrendben legyenek.

===Buborék-rendezés===

* Algoritmus:
** Procedure buborék
		  <pre>
for (j=n-1, j>0, j:=j-1) do
	 for (i=1, i<=j, i:=i+1) do
		  { ha A[i+1]&lt; A[i], akkor cseréljük ki őket. }
		  </pre>
* 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> &gt; k/2, ezt kell összegezni k=1,2,&#8230;,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,&#8230;,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&ge; <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<sub>n</sub>minden 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<sup>k</sup>amiből 2<sup>k</sup>&ge; 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 (&#1052;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) &le; 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,&lt;) 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}&lt;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 &le;2<sup>i-1</sup>csú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&lt;s&#8217; 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)
### Adott A[1:n] tömb és s elem, illetve i és j változók.
### i-t 1-től indítva növeljük, amíg A[i]&lt;s teljesül. Utána j-t n-től indítva csökkentjük, amíg A[j]&ge;s.
### Ha mindkettő megáll és i&lt;j, akkor felcseréljük A[i]-t és A[j]-t. i:=i+1; j:=j-1.
### Ha i&lt;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&le;n/logn) vagy k&ge;(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&le;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 &lt; reláció a komponensek rendezéséből álló lexikografikus rendezés. Pl: t1,&#8230;,tk és u1,&#8230;,uk két kulcs U-ból. t1,&#8230;,tk &gt; u1,&#8230;,uk, ha teljesül, hogy ti&gt;ui a legkisebb i indexre, amelyre ti &#8800; 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, &#8230;, 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 &lt; Y akkor
*** vagy x1&lt;y1, ekkor a 2. rendezés biztosítja a helyes sorrendet.
*** vagy (x1=x2) & (x2&lt;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&lt;&#8230;&lt;al és b1&lt;&#8230;&lt;bm sorozatokat akarjuk összefésüni c1&lt;&#8230;&lt;cl+m sorozattá.
** Párhuzamosan összefésüljük a1&lt;a3&lt;a5&lt;&#8230; és b2&lt;b4&#8230; sorozatot az u1&lt;u2&lt;u3 sorozattá, illetve az a2&lt;a4&lt;&#8230; és b1&lt;b3&lt;&#8230; sorozatot v1&lt;v2&lt;v3&#8230; 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)&le; <math> \lceil{log_2n}\rceil </math> (Tp(n) &le; 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<sup>2</sup>n) (biz: tp(n) &le; 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.

-- [[SomodiTibor|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. -- [[CzinderAttila|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 -- [[TothTamas|Tommey]] - 2007.01.02.


[[Category:Infoalap]]