2008 tavasz

Haladó rendezések [email protected] PPT 2007/2008 tavasz http://nik.bmf.hu/ppt 1

Témakörök Alapvető összehasonlító rendezések Shell rendezés Kupacrendezés Leszámláló rendezés Radix rendezés Edényrendezés

2

Rendezés fogalma • Alapfeladat: Egy A nevű N elemű sorozat elemeinek nagyság szerinti sorrendbe rendezése • Feltételezzük: – A sorozat elemei olyanok, amelyekre a <, ≤ relációk léteznek. – A sorozathoz létezik indexelés művelet

• A módszerek összehasonlításának alapja: – tárigény – idő (végrehajtott műveletek száma) – (bonyolultság)

• Általunk tárgyalt típusok – összehasonlító rendezések – nem összehasonlító rendezések

3

Egyszerű cserés rendezés Eljárás Rendezés(N, A) Ciklus i ← 1-től N-1-ig Ciklus j ← i+1-től N-ig Ha A[i] > A[j] akkor A[i] ↔ A[j] Elágazás vége Ciklus vége Ciklus vége Eljárás vége

• Tárigény: • Lépésszám – Hasonlítás: – Mozgatás:

N+1 N*(N-1)/2 0 – 3*N*(N-1)/2

O(n2) O(n2) 4

Minimumkiválasztásos rendezés Eljárás Rendezés(N, A) Ciklus i ← 1-től N-1-ig MIN ← i Ciklus j ← i+1-től N-ig Ha A[MIN] > A[j] akkor MIN ← j Ciklus vége A[i] ↔ A[MIN] Ciklus vége Eljárás vége


N+1 N*(N-1)/2 0 – 3*(N-1)

O(n2) O(n) 5

Buborékos rendezés Eljárás Rendezés(N, A) Ciklus i ← N-től 2-ig Ciklus j ← 1-től i-1-ig Ha A[j] > A[j+1] akkor A[j] ↔ A[j+1] Elágazás vége Ciklus vége Ciklus vége Eljárás vége


N+1 N*(N-1)/2 0 – 3*N*(N-1)/2

O(n2) O(n2) 6

Javított buborékos rendezés Eljárás Rendezés(N, A) i ← N Ciklus amíg i ≥ 2 CS ← 0 Ciklus j ← 1-től i-1-ig Ha A[j] > A[j+1] akkor A[j] ↔ A[j+1] CS ← j Elágazás vége Ciklus vége i ← CS Ciklus vége Eljárás vége

Tárigény: N+1

Hasonlítás: O(n2)

Mozgatás: O(n2) 7

Beillesztéses rendezés Eljárás Rendezés(N, A) Ciklus i ← 2-től N-ig j ← i-1 Ciklus amíg (j ≥ 0) és (A[j] > A[j+1]) A[j] ↔ A[j+1] j ← j - 1 Ciklus vége Ciklus vége Eljárás vége

Tárigény: N+1

Hasonlítás: O(n2)

Mozgatás: O(n2)

8

Javított beillesztéses rendezés Eljárás Rendezés(N, A) Ciklus i ← 2-től N-ig j ← i-1 Y ← A[i] Ciklus amíg (j ≥ 0) és (A[j] > Y) A[j+1] ← A[j] j ← j - 1 Ciklus vége A[j+1] ← Y Ciklus vége Eljárás vége

Tárigény: N+1

Hasonlítás: O(n2)

Mozgatás: O(n2)

9


10

Shell rendezés Eljárás Rendezés(N, A, L0) L ← L0 Ciklus amíg L ≥

1

Ciklus k ← L+1-től 2*L-ig Ciklus i ← k-tól N-ig L-esével j ← i – L; y ← A[i] Ciklus amíg (j > 0) és (A[j] > y) A[j + L] ← A[j]; j ← j – L Ciklus vége A[j + L] ← y Ciklus vége Ciklus vége L ← Következő_L(L) Ciklus vége Elágazás vége

Lépésszám:

O(n*log2n) 11


12

Kupac adatszerkezet • Bináris kupac: Egy majdnem teljes bináris fa egy tömbben ábrázolva • A tömb mérete = kupac mérete = N 1 2 4

3

1 2 3 4 5

5

• Fa – kupac megfeleltetés – Szülő(i) : i / 2 – Bal(i) :2*i – Jobb(i) : 2 * i + 1 13

Kupac tulajdonság • Kupac tulajdonság: A kupac minden i, gyökértől különböző eleme esetén: A[Szülő(i)] ≥ A[i] • Tehát egy olyan bináris fát képvisel, amelyre igaz, hogy minden csúcs bal és jobb oldali részfájában csak kisebb vagy egyenlő értékek találhatók. • Ez nem azonos a tanult bináris keresőfa 20 adatszerkezettel! 18 8

14 16

14

Kupactulajdonság fenntartása • Kupacol: Eljárás Kupacol(A, i, N) b ← Bal(i); j ← Jobb(i) Ha b ≤ N és A[b] > A[i] akkor MAX ← b különben MAX ← i Ha j ≤ N és A[j] > A[MAX] akkor MAX ← j Ha MAX ≠ i akkor A[i] ↔ A[MAX] Kupacol(A, MAX, N) Elágazás vége Eljárás vége

• Feltételezzük, hogy a bal és jobb oldali részfák kupac szerkezetűek. Ha A[i] kisebb valamelyik gyerekénél, akkor megsérti a kupactulajdonságot. 15

Kupac építése • Kupacot-épít: Eljárás Kupacot-épít(A) N ← Tömb_méret(A) Ciklus i ← N/2-től 1-ig Kupacol(A, i, N) Ciklus vége Eljárás vége

• Az A tömböt alulról felfelé haladva kupaccá alakítjuk • Az N/2-től N-ig terjedő index elemek levelek, tehát egy elemű (a kupactulajdonságot teljesítő) fáknak tekinthetőek, így csak a többi csúcsot kell ellenőrizni • A feldolgozás sorrendje garantálja a Kupacol eljárás előfeltételét 16

A kupacrendezés • Kupacrendezés: Eljárás Kupacrendezés(A) Kupacot-épít(A) Ciklus i ← N-től 2-ig A[1] ↔ A[i] N ← N – 1 Kupacol(A, 1, N) Ciklus vége Eljárás vége

• A kupacban a gyökérelem biztosan a legnagyobb • Ötlet: ezt helyezzük a tömb végére, zárjuk ki a kupacból, majd a maradék elemekből építsünk újra kupacot 17

Kupacba beszúrás • Kupacba-beszúr: Eljárás Kupacba-beszúr(A, kulcs) N ← N + 1 i ← N Ciklus amíg (i > 1) és (A[Szülő(i)] < kulcs) A[i] ← A[Szülő(i)] i ← Szülő(i) Ciklus vége A[i] ← kulcs Eljárás vége

• A kupac kibővítése után beszúró rendezésnél látott módon megkeresi az új kulcs helyét a kupacban 18

Kupacrendezés elemzése • A kupacrendezés futási ideje: O(n*lgn) • Összehasonlító rendezés • Műveletei: • • • •

Beszúrás Maximum Kivesz-maximum Kupacba-beszúr

• Gyakorlati alkalmazása: elsőbbségi sorok

19


20

Szétosztó rendezés • Feltételezzük, hogy a kulcsok 1 és N közötti egész számok, és nincs két azonos kulcsú rekord Eljárás Szétosztó-rendezés(A, B, N) Ciklus i ← 1-től N-ig B[A[i].kulcs] ← A[i] Ciklus vége Eljárás vége

• Lépésszám: O(n) • Ha a kulcsok nem fedik le teljesen az 1 .. N intervallumot, akkor kezelni kell az üres helyeket az eredményben

21

Leszámláló rendezés Eljárás Leszámláló-rendezés(A, B, N, K) C[] ← 0 Ciklus i ← 1-től N-ig C[A[i].kulcs] ← C[A[i].kulcs] + 1 Ciklus vége Ciklus i ← 2-től K-ig C[i] ← C[i] + C[i-1] Ciklus vége Ciklus i ← N-től 1-ig B[C[A[i].kulcs]] ← A[i] C[A[i].kulcs] ← C[A[i].kulcs] – 1 Ciklus vége Eljárás vége

Lépésszám:

O(n) 22

Leszámláló rendezés - bemenet A

B C

2 Peti 3 Kati 1 Feri 4 Mari 1 Mici 5 Laci 1 Móni 1 Pali 4 Béni 5 Sanyi 2 Tóni 3 Teri

23

Leszámláló rendezés – 1. lépés A

B C


4 2 2 2 2

24


B C


4 6 8 10 12

25


B C


4 6 7 10 12

3

Teri

26

Leszámláló rendezés – 3-2. lépés A

B C


4 5 7 10

2

Tóni

12

3

Teri

27

Leszámláló rendezés – 3-N. lépés A

B C


0 4 6 8 10

1 Feri 1 Mici 1 Móni 1 Pali 2 Peti 2 Tóni 3 Kati 3 Teri 4 Mari 4 Béna 5 Laci 5 Sanyi

Stabil: megtartja az azonos kulcsú elemek sorrendjét! 28


29

Radix (számjegyes) rendezés • Radix rendezés Eljárás Radix-rendezés(A, D) Ciklus j ← 1-től D-ig {Stabil rendezés az i. „számjegyen”} Ciklus vége Eljárás vége

• Paraméterei – A – rendezendő számokat tartalmazó tömb – D – „számjegyek” darabszáma

• Azonos hosszúságú számok, szövegek, struktúrák esetén használható • Lépésszám: O(n) 30

Radix rendezés menete Eredeti

1. lépés

2. lépés

3. lépés

412 657 542 211 457 554 154 551 151 154 134 382

211 551 151 412 542 382 554 154 154 134 657 457

211 412 134 542 551 151 554 154 154 657 457 382

134 151 154 154 211 382 412 457 542 551 554 657 31

Radix rendezés a gyakorlatban • Gyakorlati megvalósítások: – – – –

Régen lyukkártyák Számjegyenkénti rendezés Szövegek rendezése Dátumok rendezése (év-hó-nap)

• Ha nem azonos hosszúságú minden szó, a rövidebbek elejét ki kell egészíteni!

32


33

Edényrendezés • Edényrendezés Eljárás Edény-rendezés(A, N) Ciklus i ← 1-től N-ig Listába_beszúrás(B[f(A[i])], A[i]) Ciklus vége Ciklus i ← 1-től M ig Lista_rendezés(B[i]) Ciklus vége Ciklus i ← 1-től M ig Lista_összefűzés(C, B[i]) Ciklus vége Eljárás vége

34

Edényrendezés a gyakorlatban • Akkor alkalmazható hatékonyan, ha a bemenet elemei egy megfelelő hasító függvény segítségével egyenletesen oszthatók el egy 1..M intervallumon Ideális esetben M = N • Amennyiben az elosztás egyenletes, az egyes elemekben található láncolt listák elemtartalma kicsi lesz, így azok rendezése gyorsan végrehajtható

35

Javasolt/felhasznált irodalom • Cormen, Leiserson, Rivest: Algoritmusok Műszaki Könyvkiadó, 1997 • Pap, Szlávi, Zsakó: µlógia34 – Módszeres programozás ELTE TTK, 2002 • Knuth: A számítógép programozás művészete 3. Műszaki Könyvkiadó, 1988

36

2008 tavasz

Recommend Documents