Ferrero, 2013. január 29., 19:05-n

2013-01-29T19:05:45Z

← Régebbi változat		A lap 2013. január 29., 21:05-kori változata
1. sor:		1. sor:
	~~{{GlobalTemplate\|Infoalap\|AlgElRendezesKeresesOsszefoglalo}}~~


	__TOC__		__TOC__

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElRendezesKeresesOsszefoglalo}} TOC < reláció: rendezés
(U,<) pár: rendezett halmaz ill. típus ==Keresés rendezett…”

2012-10-21T19:52:20Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElRendezesKeresesOsszefoglalo}} __TOC__ < reláció: rendezés (U,<) pár: rendezett halmaz ill. típus ==Keresés rendezett…”

Új lap

{{GlobalTemplate|Infoalap|AlgElRendezesKeresesOsszefoglalo}}

__TOC__

< 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.

<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…
* 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
<pre>
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. }
</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> > 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)
### 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]<s teljesül. Utána j-t n-től indítva csökkentjük, amíg A[j]≥s.
### Ha mindkettő megáll és i<j, akkor felcseréljük A[i]-t és A[j]-t. i:=i+1; j:=j-1.
### 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.

-- [[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]]

Keresés és rendezés - Laptörténet

Ferrero, 2013. január 29., 19:05-n

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElRendezesKeresesOsszefoglalo}} __TOC__ < reláció: rendezés (U,<) pár: rendezett halmaz ill. típus ==Keresés rendezett…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElRendezesKeresesOsszefoglalo}} TOC < reláció: rendezés
(U,<) pár: rendezett halmaz ill. típus ==Keresés rendezett…”