Tartalom. Programozási alapismeretek. 11. előadás

Tartalom  Rendezési

feladat – specifikáció 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ő  Egyszerű

Programozási alapismeretek

ELTE

11. előadás

11-11-16

Szlávi- Zsakó: Programozási alapismeretek 11.

Rendezések

Rendezési feladat

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

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

11-11-16

ELTE

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? Szlávi-Zsakó: Szlávi-Zsakó: Programozási alapismeretek 11.

3/28

a specifikációban: Ha egy adat előfordul a bemeneten és kimene-ten is, akkor az UF-ben együtt kell előfordul-nia 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.

11-11-16


Egyszerű cserés rendezés

Algoritmus:

 Hasonlítsuk

11-11-16

az első ele-met az összes mögötte levővel, s ha kell, cse-réljük meg!  Ezután ugyanezt X csi-náljuk a második A pirossal jelöltek már a helyükön A pirossal jelöltek már a helyükön elem-re! vannak vannak … XXX…  Végül az utolsó két elemre! Szlávi-Zsakó: Szlávi-Zsakó: Programozási alapismeretek 11.

4/28

Egyszerű cserés rendezés

A lényeg:

ELTE

2/28

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

 Hasonlítások  Mozgatások 5/28

11-11-16

N

N 1 2

N száma: 1+2+..+N–1=

N  száma: 03…


N 1 2

6/28

Minimumkiválasztásos rendezés

Minimumkiválasztásos rendezés

Algoritmus:

A lényeg:  Vegyük

ELTE

az első elem mögöttiek minimumát, s cseréljük meg az elsővel, ha kell!  Ezután ugyanezt csináljuk a második X elemre! A pirossal jelöltek már a helyükön … vannak  Végül az utolsó két XXX… elemre!

11-11-16

Szlávi-Zsakó: Szlávi-Zsakó: Programozási alapismeretek 11.

7/28

Minimum-kiválasztás

Min:=i I

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

Elem-csere

N 1 száma: 1+2+..+N–1= N 2  Mozgatások száma: 3(N–1) 11-11-16


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

A többiek is tartanak a helyük felé.

X

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

…XXX


9/28

11-11-16


10/28 10/28

Javított buborékos rendezés i:=N i≥2 cs:=0

ELTE

y 11-11-16

ósl ot u z A l eher esc

12/28 12/28

es

I

éz y gejl ef

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 biz-tosan jó elemek vannak, a külső ciklusvál-tozóval többet is léphetünk.

Algoritmus:

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

 Ha


N

 Hasonlítások

Megfigyelések:

11-11-16

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

Elem-csere

ELTE

Javított buborékos rendezés

ELTE

8/28

Buborékos rendezés

 Hasonlítsunk

11-11-16

N



 Hasonlítások

A lényeg:

ELTE

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

ELTE

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

i=1..N–1

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 Szlávi- Zsakó: Programozási alapismeretek 11.

N



13/28 13/28

Beillesztéses rendezés

Beillesztéses rendezés

Algoritmus:

A lényeg:  Egy

ELTE

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!

X

i=2..N j:=i–1 j>0 és X[j]>X[j+1] S:=X[j] X[j]:=X[j+1] X[j+1]:=S j:=j–1

Elem-csere ELTE

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

11-11-16


14/28 14/28

11-11-16

Javított beillesztéses rendezés

elem rendezett. 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 iediket; így már i darab rendezett lesz. …  Az utolsóval ugyanígy! A

ELTE

Algoritmus:

X

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 2 N 1  Mozgatások száma: 2(N–1) (… N  4)  2  Hasonlítások

11-11-16


16/28 16/28

11-11-16

Szétosztó rendezés

N száma: N–1 …


17/28 17/28

Szétosztó rendezés Algoritmus:

A lényeg:

ELTE

15/28 15/28

Javított beillesztéses rendezés

A lényeg:  Egy


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)

i=1..N Y[X[i]]:=X[i] ELTE

 Persze

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:Egész, …)]

Algoritmus:i=1..N

Y[X[i].kulcs]:=X[i]

11-11-16


18/28 18/28

11-11-16


19/28 19/28

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


Előfeltétel:

A lényeg:

a rendezendő értékek 1 és M közötti egész számok.

ELTE

11-11-16

Specifikáció:

ELTE

 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) Szlávi-Zsakó: Szlávi-Zsakó: Programozási alapismeretek 11.

 Első

20/28 20/28

11-11-16

lépésben számoljuk meg, hogy melyik értékből hány van a rendezendő sorozatban!  Ezután adjuk meg, hogy az utolsó i értéket hova kell tenni!  Ez pontosan az i-nél kisebb vagy egyenlő számok száma a sorozatban!  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ít-sunk: az utolsó i értékű elemet ettől kezdve eggyel kisebb helyre kell tenni. Szlávi- Zsakó: Programozási alapismeretek 11.


Számláló rendezés

Algoritmus:

A lényeg:

Db[1..M]:=0

 Ha

i=1..N Db[X[i]]:=Db[X[i]]+1 ELTE

21/28 21/28

ELTE

i=2..M Db[i]:=Db[i–1]+Db[i] i=1..N Y[Db[X[i]]]:=X[i] Db[X[i]]:=Db[X[i]]–1

nem megy a szétosztó rendezés, akkor segítsünk magunkon, először számláljunk, 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.-től balra levő, vele egyenlő elemek számát!

 Mozgatások  Additív 11-11-16

száma: N műveletek száma: 2M–2+2N


22/28 22/28

11-11-16


Rendezések hatékonysága

Számláló rendezés

ELTE

11-11-16

Algoritmus:

N2 idejű rendezések:

i=1..N–1 j=i+1..N X[i]>X[j] I N Db[i]:=Db[i] Db[j]:=Db[j]+1 +1 i=1..N Y[Db[i]]:=X[i] 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

 Egyszerű


23/28 23/28

24/28 24/28

cserés rendezés  rendezés

 Minimum-kiválasztásos ELTE

  Buborékos

rendezés buborékos rendezés  Beillesztéses rendezés  Javított beillesztéses rendezés  Számláló rendezés  Javított

11-11-16


     25/28 25/28

Rendezések hatékonysága

Az évfolyamZh A minta letöltése:

N (N+M) idejű rendezések: (de speciális feltétellel ) ELTE

11-11-16

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!

http://progalap.elte.hu/downloads/kov /progalap_evfzh_minta.zip

 Szétosztó


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

26/28 26/28

ELTE

vagy http://people.inf.elte.hu/szlavi/BscPro gAlap/MintaZh.zip

és a „partitúra”: http://progalap.elte.hu/downloads/kov /progalap_evfolyamzh_teszteles.pdf 11-11-16


27/28 27/28

Tartalom. Programozási alapismeretek. 11. előadás

Recommend Documents