Közismereti informatika I. 4. előadás
2011.09.08.
Rendezések Bemenet:
ELTE
N: Egész, X: Tömb(1..N: Egész) Kimenet: X: Tömb(1..N: Egész) Előfeltétel: Utófeltétel: Rendezett(X) és X=permutáció(X’) Az
eredmény a bemenet egy permutációja.
Rendezett(X):
i(1≤i≤N-1):
X[i]≤X[i+1] 2011.09.08.
Zsakó László: Közismereti informatika I.
2
Egyszerű cserés rendezés Hasonlítsuk
ELTE
2011.09.08.
az első elemet az összes mögötte levővel, s ha kell, cseréljük meg! Ezután ugyanezt csináljuk a második elemre! … Végül az utolsó két elemre! Zsakó László: Közismereti informatika I.
A minimum az elejére kerül.
3
Egyszerű cserés rendezés
ELTE
2011.09.08.
Rendezés: Ciklus i=1-től N-1-ig Ciklus j=i+1-től N-ig Ha X[i]>X[j] akkor Csere(X[i],X[j]) Ciklus vége Ciklus vége Eljárás vége. N 1 N Hasonlítások száma: 1+2+..+N-1= 2 N 1 Mozgatások száma: 0 – 3 N 2 Zsakó László: Közismereti informatika I.
4
Minimumkiválasztásos rendezés Vegyük
ELTE
2011.09.08.
az első elem mögöttiek minimumát, s cseréljük meg az elsővel! Ezután ugyanezt csináljuk a második elemre! … Végül az utolsó két elemre! Zsakó László: Közismereti informatika I.
5
Minimumkiválasztásos rendezés
ELTE
Rendezés: Ciklus i=1-től N-1-ig Min:=i Ciklus j=i+1-től N-ig Ha X[j]<X[Min] akkor Min:=j Ciklus vége Csere(X[i],X[Min]) Ciklus vége Eljárás vége.
N 1 Hasonlítások száma: 1+2+..+N-1= N 2 Mozgatások 2011.09.08.
száma: 3*(N-1)
Zsakó László: Közismereti informatika I.
6
Buborékos rendezés Hasonlítsunk
ELTE
2011.09.08.
minden elemet a mögötte levővel, s ha kell, cserélA maximum a jük meg! végére kerül. Ezután ugyanezt csináljuk az utolsó elem nélkül! A többbiek is tarta… nak a helyük felé. Végül az első két elemre! Zsakó László: Közismereti informatika I.
7
Buborékos rendezés
ELTE
2011.09.08.
Rendezés: Ciklus i=N-től 2-ig -1-esével Ciklus j=1-től i-1-ig Ha X[j]>X[j+1] akkor Csere(X[j],X[j+1]) Ciklus vége Ciklus vége Eljárás vége. N 1 Hasonlítások száma: 1+2+..+N-1= N 2 N 1 Mozgatások száma: 0 – 3 N 2 Zsakó László: Közismereti informatika I.
8
Javított buborékos rendezés
ELTE
2011.09.08.
Megfigyelések: Ha 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. Zsakó László: Közismereti informatika I.
9
Javított buborékos rendezés Rendezés: i:=N Ciklus amíg i>1 cs:=0 Ciklus j=1-től i-1-ig Ha X[j]>X[j+1] akkor Csere(X[j],X[j+1]) cs:=j Ciklus vége i:=cs Ciklus vége Eljárás vége.
ELTE
2011.09.08.
Zsakó László: Programozási alapismeretek
10
Rendezések
ELTE
2011.09.08.
Mit tudunk az eddigi módszerekről? A külső ciklus egy lefutása alatt legalább 1 elem a végleges helyére kerül. (Azaz például azonnal kiírhatnánk az eredménybe.) A külső ciklus egy lefutásához már ismernünk kell az összes elemet.
Zsakó László: Közismereti informatika I.
11
Beillesztéses rendezés Egy
ELTE
2011.09.08.
elem mindig rende-
zett. A másodikat vagy mögé, vagy elé tesszük. … Az i-ediket az addigiak mögé tesszük, majd addig hozzuk előre, amíg a helyére nem kerül. Az utolsóval ugyanígy! Zsakó László: Közismereti informatika I.
X
A megoldás: Keresés tétel közben cserélgetünk 12
Beillesztéses rendezés
ELTE
2011.09.08.
Rendezés: Ciklus i=2-től N-ig j:=i-1 Ciklus amíg j>0 és X[j]>X[j+1] Csere(X[j],X[j+1]); j:=j-1 Ciklus vége Ciklus vége Eljárás vége. N 1 Hasonlítások száma: N-1 – N 2 N 1 Mozgatások száma: 0 – 3 N 2 Zsakó László: Közismereti informatika I.
13
Javított beillesztéses rendezés Egy
ELTE
2011.09.08.
elem mindig rende-
X
zett. A másodikat vagy mögé, vagy elé tesszük. … Az i-ediknél kisebbeket tologassuk hátra, majd A megoldás: illesszük be eléjük az Keresés tétel i-ediket! közben Az utolsóval ugyanígy! tologatunk. Zsakó László: Közismereti informatika I.
14
Javított beillesztéses rendezés
ELTE
Rendezés: Ciklus i=2-től N-ig j:=i-1; s:=X[i] Ciklus amíg j>0 és X[j]>s X[j+1]:=X[j]; j:=j-1 Ciklus vége X[j+1]:=s Ciklus vége Eljárás vége.
N 1 Hasonlítások száma: N-1 – N 2 N 1 Mozgatások száma: 2*(N-1) – ( N 1) 2
2011.09.08.
Zsakó László: Közismereti informatika I.
15
Rendezések
ELTE
2011.09.08.
Mit tudunk a két beillesztéses rendezés változatról? A külső ciklus utolsó lefutására kerül minden elem a végleges helyére. A külső ciklus egy lefutásához elég ismernünk a következő elemet. (Azaz most például beolvasás közben is végezhetnénk a rendezést.) Zsakó László: Közismereti informatika I.
16
Szétosztó rendezés Ha a rendezendő sorozatról speciális tudásunk van, akkor próbálkozhatunk más módszerekkel is. ELTE
2011.09.08.
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: X=permutáció(1,…,N) Utófeltétel: Rendezett(Y) és Y=permutáció(X) Zsakó László: Közismereti informatika I.
17
Szétosztó rendezés
ELTE
Rendezés: Ciklus i=1-től N-ig Y[X[i]]:=X[i] Ciklus vége Eljárás vége. Persze
2011.09.08.
ehelyett írhattuk volna: Y[i]:=i!!!
Zsakó László: Közismereti informatika I.
18
Szétosztó rendezés Azaz
ELTE
2011.09.08.
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: Y: Tömb(1..N: Rekord(kulcs: Egész,…))
Rendezés: Ciklus i=1-től N-ig Y[X[i].kucs]:=X[i] Ciklus vége Eljárás vége.
Zsakó László: Közismereti informatika I.
19
Számlálva szétosztó rendezés
ELTE
Most azt tételezzük fel, hogy a rendezendő értékek tetszőleges 1 és M közötti egész számok (vagy azzá transzformálhatók). Bemenet:
N,M: Egész, X: Tömb(1..N: Egész) Kimenet: Y: Tömb(1..N: Egész) Előfeltétel: i(1iN): 1X[i]M Utófeltétel: Rendezett(Y) és Y=permutáció(X) 2011.09.08.
Zsakó László: Közismereti informatika I.
20
Számlálva szétosztó rendezés Első
lépésben számoljuk meg, hogy melyik értékből hány van a rendezendő sorozatban!
ELTE
Rendezés: Db:=(0,…,0) Ciklus i=1-től N-ig Ha X[i]=1 akkor Db[1]:=Db[1]+1 Ha X[i]=1 akkor Db[1]:=Db[1]+1 … Ciklus vége … Amennyi
az X[i], annyiadik számlálót növeljük: elágazás helyett indexelés!
2011.09.08.
Zsakó László: Közismereti informatika I.
21
Számlálva szétosztó rendezés
ELTE
Rendezés: Db:=(0,…,0) Ciklus i=1-től N-ig Db[X[i]]:=Db[X[i]]+1 Ciklus vége … 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! 2011.09.08.
Zsakó László: Közismereti informatika I.
22
Számlálva szétosztó rendezés
ELTE
… ut[1]:=Db[1] Ciklus i=2-től M-ig ut[i]:=ut[i]+Db[i] Ciklus vége … 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 utolsó i értékű elemet ettől kezdve eggyel kisebb helyre kell tenni.
2011.09.08.
Zsakó László: Közismereti informatika I.
23
Számlálva szétosztó rendezés
ELTE
… Ciklus i=1-től N-ig Y[ut[X[i]]]:=X[i] ut[X[i]]:=ut[X[i]]-1 Ciklus vége Eljárás vége. Mozgatások
száma: N Összeadások száma: M+2*N
2011.09.08.
Zsakó László: Közismereti informatika I.
24
Számláló rendezés Ha
ELTE
2011.09.08.
nem megy a szétosztó rendezés, akkor segítsünk magunkon, először számoljunk, 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! Zsakó László: Közismereti informatika I.
25
Számláló rendezés
ELTE
2011.09.08.
Rendezés: Db:=(0,…,0) Ciklus i=1-től N-1-ig Ciklus j=i+1-től N-ig Ha X[i]>X[j] akkor Db[j]:=Db[j]+1 különben Db[i]:=Db[i]+1 Ciklus vége Ciklus vége Ciklus i=1-től N-ig Y[Db[X[i]]:=X[i] Ciklus vége Eljárás vége.
N 1 Hasonlítások száma: 1+2+..+N-1= N 2 Mozgatások száma: N Zsakó László: Közismereti informatika I.
26
Rendezések N2 idejű rendezések: Egyszerű ELTE
2011.09.08.
cserés rendezés Minimumkivá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 Zsakó László: Közismereti informatika I.
27
Rendezések N (N+M) idejű rendezések: (de speciális előfeltétellel) Szétosztó ELTE
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! 2011.09.08.
Zsakó László: Közismereti informatika I.
28
Közismereti informatika 4. előadás vége
2011.09.08..
