Programozási alapismeretek 11. előadás

Programozási alapismeretek 11. előadás

Tartalom  Rendezési

ELTE

2013.11.26.

feladat – specifikáció  Egyszerű cserés rendezés  Minimum-kiválasztásos rendezés  Buborékos rendezés  Javított buborékos rendezés  Beillesztéses rendezés  Javított beillesztéses rendezés  Szétosztó rendezés  Számlálva szétosztó rendezés  Rendezések hatékonysága – idő Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

2/30

Rendezési feladat Specifikáció:  Bemenet:

ELTE

NEgész, XTömb[1..N:Valami]  Kimenet: X’Tömb[1..N:Valami]  Előfeltétel: N0  Utófeltétel: RendezettE(X’) és X’Permutáció(X)  Jelölések: o o o

2013.11.26.

X’: az X kimeneti (megálláskori) értéke RendezettE(X): X rendezett-e? X’Permutáció(X): X’ az X elemeinek egy permutációja-e? Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

3/30

Rendezések (fontos új fogalmak, jelölések)  Aposztróf

ELTE

2013.11.26.

a specifikációban: Ha egy adat előfordul a bemeneten és kimeneten is, akkor az UF-ben együtt kell előfordulnia az adat bemenetkori és kimenetkori értéke. Megkülönböztetésül a kimeneti értéket „megaposztrofáljuk”. Pl.: Z’:=a Z kimeneti (megálláskori) értéke.  „Rendezett-e” predikátum: RendezettE(Z): i(1≤i≤N–1): Z[i]≤Z[i+1]  Permutációhalmaz: Permutáció(Z):= a Z elemeinek összes permutációját tartalmazó halmaz. Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

4/30

Egyszerű cserés rendezés A lényeg:  Hasonlítsuk

ELTE

2013.11.26.

az első elemet az összes mögötte A minimum az „alsó” levővel, s ha kell, csevégére kerül. réljük meg!  Ezután ugyanezt csináljuk a második elemre! A pirossal jelöltek már a helyükön vannak …  Végül az utolsó két elemre! Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

5/30

Egyszerű cserés rendezés Algoritmus:

ELTE

Elem-csere

i=1..N–1 j=i+1..N X[i]>X[j] I S:=X[i] X[i]:=X[j]  X[j]:=S

Változó i,j:Egész S:Valami

N

N 1  Hasonlítások száma: 1+2+..+N–1= N  2 N 1  Mozgatások száma: 0 … 3  N  2 2013.11.26.

Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

6/30

Minimum-kiválasztásos rendezés A lényeg:  Vegyük

ELTE

2013.11.26.

az első elem és a mögöttiek minimumát, s cseréljük meg az A minimum az „alsó” végére kerül. elsővel (ha kell)!  Ezután ugyanezt csináljuk a második elemre! … A pirossal jelöltek már a helyükön vannak  Végül az utolsó két elemre! Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

7/30

Minimum-kiválasztásos rendezés Algoritmus: Minimumkiválasztás az i.-től

i=1..N–1 MinI:=i

ELTE

I

Elem-csere

Változó MinI, i,j:Egész S:Valami

j=i+1..N X[MinI]>X[j]

MinI:=j S:=X[i] X[i]:=X[MinI] X[MinI]:=S



N

N 1  Hasonlítások száma: 1+2+..+N–1= N  2  Mozgatások száma: 3(N–1) 2013.11.26.


8/30

Buborékos rendezés A lényeg:  Hasonlítsunk

ELTE

2013.11.26.

minden elemet a mögötte levővel, s ha kell, cseréljük meg!  Ezután ugyanezt csináljuk az utolsó elem nélkül! …  Végül az első két elemre!

A maximum a „felső” végére kerül.

A többiek is tartanak a helyük felé. A pirossal jelöltek már a helyükön vannak


9/30

Buborékos rendezés Algoritmus:

ELTE

Elem-csere

i=N..2, -1-esével j=1..i–1 X[j]>X[j+1] I S:=X[j] X[j]:=X[j+1]  X[j+1]:=S


N

N 1  Hasonlítások száma: 1+2+..+N–1= N  2 N 1  Mozgatások száma: 0 … 3  N  2 2013.11.26.


10/30

Javított buborékos rendezés Megfigyelések:  Ha

ELTE

2013.11.26.

a belső ciklusban egyáltalán nincs csere, akkor be lehetne fejezni a rendezést.  Ha a belső ciklusban a K. helyen van az utolsó csere, akkor a K+1. helytől már biztosan jó elemek vannak, a külső ciklusváltozóval többet is léphetünk.


11/30

Javított buborékos rendezés

Átírás ‘amíg’-os ciklussá

Algoritmus:

Változó cs, i,j:Egés S:Valam

i:=N i≥2 cs:=0

ELTE

Az utolsó cserehely feljegyzése

I

2013.11.26.

j=1..i–1 X[j]>X[j+1]

S:=X[j] X[j]:=X[j+1] X[j+1]:=S cs:=j i:=cs Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

N



13/30

Beillesztéses rendezés A lényeg:  Egy

ELTE

2013.11.26.

elem rendezett.  A másodikat vagy mögé, vagy elé tesszük, így már ketten is rendezettek. …  Az i-ediket a kezdő, i–1 rendezettben addig hozzuk előre cserékkel, amíg a helyére nem kerül; így már i darab rendezett lesz. …  Az utolsóval ugyanígy! Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

14/30

Beillesztéses rendezés Algoritmus: i=2..N j:=i–1 Elem-csere ELTE

2013.11.26.


j>0 és X[j]>X[j+1] S:=X[j] X[j]:=X[j+1] X[j+1]:=S j:=j–1

N 1  Hasonlítások száma: N–1 … N  2 N 1  Mozgatások száma: 0 … 3  N  2 Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

15/30

Javított beillesztéses rendezés

A lényeg:  Egy

ELTE

2013.11.26.

elem rendezett.  A másodikat vagy mögé, vagy elé tesszük, így már ketten is rendezettek. …  Az i-ediknél a nála kisebbeket tologassuk hátra, majd illesszük be eléjük az i-ediket; így már i darab rendezett lesz. …  Az utolsóval ugyanígy! Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

16/30

Javított beillesztéses rendezés Algoritmus: i=2..N

S:=X[i] j:=i–1 ELTE

Elem-mozgatás, nem csere!


j>0 és X[j]>s X[j+1]:=X[j] j:=j–1 X[j+1]:=S

N 1  Hasonlítások száma: N–1 … N  2 N 1  Mozgatások száma: 2(N–1) … ( N  4)  2 2013.11.26.


17/30

Szétosztó rendezés A lényeg:

ELTE

2013.11.26.

Ha a rendezendő sorozatról speciális tudásunk van, akkor megpróbálkozhatunk más módszerekkel is. Specifikáció – rendezés N lépésben:  Bemenet: NEgész, XTömb[1..N:Egész]  Kimenet: YTömb[1..N:Egész]  Előfeltétel: N0 és XPermutáció(1,…,N)  Utófeltétel: RendezettE(Y) és YPermutáció(X) Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

18/30

Szétosztó rendezés Algoritmus: i=1..N Y[X[i]]:=X[i] ELTE

ehelyett írhattuk volna: Y[i]:=i!   Azaz a feladat akkor érdekes, ha pl. X[i] egy rekord, aminek az egyik mezője az 1 és N közötti egész szám: X,YTömb[1..N:Rekord(kulcs:1..N,…)]  Persze

Algoritmus: i=1..N Y[X[i].kulcs]:=X[i] 2013.11.26.

Változó i:Egész


Változó i:Egész

19/30

Számlálva szétosztó rendezés Előfeltétel: a rendezendő értékek 1 és M közötti egész számok, ismétlődhetnek.

Specifikáció: ELTE

2013.11.26.

 Bemenet:

N,MEgész, XTömb[1..N:Egész]  Kimenet: YTömb[1..N:Egész]  Előfeltétel: N0 és M1 és i(1iN): 1X[i]M  Utófeltétel: RendezettE(Y) és YPermutáció(X) Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

20/30

Számlálva szétosztó rendezés A lényeg:  Első

ELTE

2013.11.26.

lépésben számláljuk meg, hogy melyik értékből hány van a rendezendő sorozatban!  Ezután adjuk meg, hogy az első „i” értéket hova kell tenni: ez pontosan az i-nél kisebb számok száma a sorozatban +1 !  Végül nézzük végig újra a sorozatot, s az „i” értékű elemet tegyük a helyére, majd módosítsunk: az első i értékű elemet ettől kezdve eggyel nagyobb helyre kell tenni. Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

21/30

Számlálva szétosztó rendezés

Algoritmus:

ELTE

Db[1..M]:=0 [Db[i]: hány darab van i-ből?] i=1..N Db[X[i]]:=Db[X[i]]+1 Első[1]:=1 i=2..M Első[i]:=Első[i–1]+Db[i–1] [Első[i]: hol az i. elsője?] i=1..N Y[Első[X[i]]]:=X[i] Első[X[i]]:=Első[X[i]]+1

Változó i:Egés Db, Első:T

 Mozgatások

száma: N  Additív műveletek száma: 3M–3+2N 2013.11.26.


22/30

Számláló rendezés A lényeg:  Ha

ELTE

2013.11.26.

nem megy a szétosztó rendezés (ismeretlen az M), akkor segítsünk magunkon, először számláljunk („sorrendet”), azután osszunk szét!  Ehhez használhatjuk a legegyszerűbb, cserés rendezés elvét.  Jelentse Db[i] az i. elemnél kisebb, vagy az i.kel egyenlő, de tőle balra levő elemek számát! ↓ A Db[i]+1 használható az i. elemnek a rendezett sorozatbeli indexeként. Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 11.

23/30

Számláló rendezés Algoritmus:

Válto i,j:E Db:

Db[1..N]:=0

ELTE

i=1..N–1 j=i+1..N X[i]>X[j] I Db[i]:=Db[i]+1 Db[j]:=Db[j]+1 i=1..N Y[Db[i]+1]:=X[i]

N

N 1  Hasonlítások száma: 1+2+..+N–1= N  2

 Mozgatások

száma: N  Additív műveletek száma: hasonlítások száma 2013.11.26.


24/30

Rendezések hatékonysága N2 idejű rendezések:  Egyszerű

ELTE

2013.11.26.

cserés rendezés  Minimum-kiválasztásos rendezés  Buborékos rendezés  Javított buborékos rendezés  Beillesztéses rendezés  Javított beillesztéses rendezés  Számláló rendezés


      

25/30

Rendezések hatékonysága N (N+M) idejű rendezések: (de speciális feltétellel) rendezés   Számlálva szétosztó rendezés  Kitekintés: (Algoritmusok tantárgy)  Lesznek Nlog(N) idejű rendezések.  Nem lehet Nlog(N)-nél jobb általános rendezés!  Szétosztó ELTE

http://cow.ceng.metu.edu.tr/Courses/download_c ourseFile.php?id=5451  http://www.sorting-algorithms.com/ 

2013.11.26.


26/30

Az évfolyamZh Tudnivalók: a main.cpp fájlt egy web-es felületen kell beküldeni (akár többször is!) és ott lehet megnézni a kapott értékelést;  ide a zh-t író az EHA-kódjával (pontosabban a laborokban érvényes kódjával) léphet majd be a saját jelszavával;  a program standard inputról olvas, standard outputra ír, a tesztelést be- és kimenet átirányítással oldjuk meg;  a bemenet biztosan helyes, ellenőrizni nem kell;  a kimenetre csak az eredményeket szabad kiírni, semmi egyebet nem;  a bemenet és a kimenet szintaxisa és sorrendje is rögzített, attól eltérni nem szabad. 

ELTE

2013.11.26.


27/30

Az évfolyamZh Edzeni való: 

A zh-ra – technikailag – fel lehet készülni az alábbi linken keresztül: http://biro.inf.elte.hu/Progalap/

ELTE

2013.11.26.


28/30

Az évfolyamZh Edzeni való: 

Néhány, jellegzetes lépés:

ELTE

2013.11.26.


29/30

Programozási alapismeretek 11. előadás vége

Programozási alapismeretek 11. előadás

Recommend Documents