Adatszerkezetek Nevezetes algoritmusok (Keresések, rendezések)
Keresések •
• • •
A probléma általános megfogalmazása: Adott egy N elemű sorozat, keressük meg azt az elemet (határozzuk meg a helyét a sorozatban), mely megfelel egy megadott tulajdonságnak. Ha több ilyen van, akkor a keresőalgoritmusok általában az első ilyen elemet találják meg. A konkrét megvalósításoknál mi egy adott értéket keresünk. Típusok: 1. Lineáris keresés (szekvenciális) 2. Bináris keresés (logaritmikus, kettéosztásos)
2
1. Lineáris keresés rendezetlen elemhalmazban • Legegyszerűbb keresés, az értéksorozatról nem tételezünk fel semmit. • Az értéksorozat első elemétől indul, és megnézi, hogy az első elem-e a keresett érték. Ha igen megtaláltam, ha nem megyek tovább – amíg meg nem találtam vagy – el nem fogynak az elemek.
• Rendezetlen elemhalmaz esetén csak az összes elem vizsgálata után jelenthetem ki, hogy nincs az értéksorban a kereset elem. • Átlagos lépések száma: n/2+1 5 2 9 6 35 4 76 22 1 58 3
1. Lineáris keresés rendezetlen elemhalmazban Iteratív változat: T tulajdonságú elemet keressük A[1..N] elemei között. Eljárás LineárisKeresés H:=0 I:=1 Ciklus amíg (I≤N) and (H=0) Ha A[I] T tulajdonságú akkor H:=I I:=I+1 Ciklus vége Eljárás vége
4
1. Lineáris keresés rendezetlen elemhalmazban Rekurzív változat: Lineáris_keresés H:=0 I:=1: Linker(I) Ha (I≤N) akkor H:=I Eljárás vége Linker(I) Ha (I≤N) and (A(I) nem T tulajdonságú) akkor I:=I+1 Linker(I) Elágazás vége Eljárás vége
5
2. Lineáris keresés rendezett elemhalmazban • Rendezett értéksorozatot tételezünk fel. • Kiindulok az első elemtől, és azt vizsgálom, hogy az-e a keresett elem. Ha az megállok, különben megyek tovább – amíg meg nem találtam, – vagy míg el nem érek egy olyan elemet, amely rendezettség szempontjából már követi a keresett elemet. 3 4 7 23 34 56 57 60 63 73 77 6
Bináris keresés Előfeltétel: – –
A sorozat rendezett. Bármelyik elem a többitől függetlenül elérhető legyen.
Algoritmus: 1. Meghatározzuk a középső elemet, majd megvizsgáljuk ez-e a keresett. Ha igen, kész vagyunk. 2. Ha nem, akkor – –
•
ha a keresett kisebb a középsőnél, akkor a sorozat alsó, egyébként a felső részében folytatjuk a keresést ugyanezzel a módszerrel.
A keresés két esetben fejeződhet be: – –
megtaláltuk a keresett adatot; Egyelemű sorozathoz jutottunk, mely nem egyezik meg a keresett elemmel. 7
Példa Keresendő: 18 7 8 12 15 16 18 21 27 29 33 34 37 51 57 58 59 62 7 8 12 15 16 18 21 27 18 21 27 18 Keresendő: 24 7 8 12 15 16 18 21 27 29 33 34 37 51 57 58 59 62 7 8 12 15 16 18 21 27 18 21 27 27 ≠ 24
1000 elemnél már 10 lépés után meg tudom mondani, hogy benne vane az adott elem. Összehasonlítások száma: (log2n)+1 8
Rendezés • A rendezési feladatok általános problémája: Adott egy n elemű sorozat, készítsük el ezeknek az elemeknek egy olyan permutációját, amelyre igaz, hogy a sorozat i. eleme kisebb (egyenlő) az i+1-ediktől. • Ez a növekvő rendezés. Az ilyen algoritmusok értelemszerűen átalakíthatók csökkenő sorrendűvé. • A különböző rendezések leginkább a következő két művelet alkalmazásában térnek el egymástól: – összehasonlítás – két sorozatelem viszonyának meghatározása, – mozgatás – az elemek sorrendjének változtatása a rendezettségnek megfelelően.
• A hatékonyság vizsgálatakor is ez a két művelet, valamint az igényelt tárterület érdekes számunkra. 9
Rendezési eljárások csoportosítása Az algoritmusban szereplő fő tevékenység szerint: 1. 2. 3. 4. 5.
Leszámoló rendezések Beszúró rendezések Cserélő rendezések Kiválasztó rendezések Összefésülő rendezések
10
1. Leszámoló rendezések • Alapötlet különböző elemek esetén: – A j. elem a rendezett sorozatban pontosan j-1 másik elemnél lesz nagyobb. – Ha egy elem pontosan k másiknál nagyobb, akkor a rendezés után a (k+1). helyre kerül. • Állapítsuk meg, hogy a vizsgált elemnél hány kisebb van. (Azonos elemeknél a kisebb indexű kisebb.) • Önmagával nem kell hasonlítani. 11
1.1. Összehasonlítva leszámoló rendezés • Használjunk egy segédtömböt, melyet először nullázzunk le, ebben számoljuk, hogy a vizsgált elemet hány kisebb (vagy egyenlő) előzi meg. 3
7
1
4
5
1
2
3
4.
2
5
0
5
6
1
2
4
0
0
0
0
0
0
0
0
3.
3
6
0
5
6
1
2
4
8.
0
1
0
1
1
0
0
4
2.
3
7
0
5
6
1
2
4
7.
1
2
0
2
2
0
2
4
6.
2
3
0
3
3
1
2
4
5.
2
4
0
3
6
1
2
4
+1
12
2. Beszúró rendezések • Egy már rendezett sorozatban keressük meg az új elem helyét, ahova aztán „beszúrjuk”. • Egyik legfontosabb osztály. • Alaptípusai – 2.1. Közvetlen beszúró rendezés – 2.2. Beszúró rendezés láncolással – 2.3. Shell rendezés
13
2.1. Közvetlen beszúró rendezés 1. Veszem az első elemet, az önmagában rendezett. 2. Mindaddig míg van elem veszem a köv. elemet és megkeresem a helyét a már rendezett elemek között. 5 3 1 4 2 Hatékonyság javítható, ha egy elem 3 5 1 4 2 helyének a megkeresésére a bináris 1 3 5 4 2 keresést alkalmazzuk. 1 3 4 5 2 1 2 3 4 5 14
2.2. Beszúró rendezés láncolással • A közvetlen beszúró rendezésnél a szekvenciális tárolás miatt az elemek mozgatása időigényes. • Használjunk láncolt listát, így csak néhány címet kell megváltoztatni.
15
2.3. Shell rendezés (fogyó növekményes rendezés) • A beszúró rendezés finomított változata. 1. Rendezzük az – –
1. elemtől minden n. elemet 2. elemtől minden n. elemet…
2. Rendezzük az – –
1. elemtől minden (n-1). elemet 2. elemtől minden (n-1). elemet…
3. … (n.) Rendezzük minden elemet beszúrással. 16
2.3. Shell rendezés (fogyó növekményes rendezés) n=4 46
57
14
44
96
25
7
70
n=2 46
25
7
44
96
57
14
70
7
25
14
44
46
57
96
70
7
14
25
44
46
57
70
96
n=1
Elemek távolsága (egy csoportban) tetszőleges, feltéve hogy szigorúan monoton csökkenő, és az utolsó távolság értéke egy. 17 Bizonyos sorozatok jobb eredményt adnak, mint mások.
3. Cserélő rendezések 3.1. Buborék rendezés • •
Szomszédok cseréjén alapul. Megvizsgáljuk a szomszédok egymáshoz való viszonyát, és ha szükséges felcseréljük őket.
Fázisok: 1. 2.
(1) ? (2), (2) ? (3), … (n-1) ? (n) ⇒ n. elem a helyén (1) ? (2), (2) ? (3), (n-2) ? (n-1) ⇒ (n-1). elem a helyén
3. … n-1.
(1) ? (2) ⇒ minden elem a helyén
18
3. Cserélő rendezések 3.1. Buborék rendezés • Helyben rendező módszer. • Időigény: n(n-1)/2 ⇒ O(n2) – Minimális, ha rendezett – Maximális, ha fordított sorrendű
• Ha egy fázisban nem volt csere ⇒ rendezett • Elegendő az előző fázis utolsó cseréjéig hasonlítgatni.
19
Példa buborék rendezésre 3. fázis
2. fázis
1. fázis 11 20
7
2
29 21
11
7
2
20 21 29
7
2
11 20 21 29
11 20
7
2
29 21
7
11
2
20 21 29
2
7
11 20 21 29
11
7
20
2
29 21
7
2
11 20 21 29
2
7
11 20 21 29
11
7
2
20 29 21
7
2
11 20 21 29
11
7
2
20 29 21
7
2
11 20 21 29
11
7
2
20 21 29 20
3. Cserélő rendezések 3.2. Gyorsrendezés • Nagy elemszámnál hatékony. • Első elem: rendezés kulcsa • Cél:
– a kulcstól balra csak ≤ elemek legyenek – a kulcstól jobbra csak ≥ elemek legyenek
• Módszer:
– Balról is keressük az első ≥ elemet – Jobbról is keressük az első ≤ elemet – Ha a balról megtalált > jobbról megtalált ⇒ csere
• Rekurzív algoritmus 21
Példa gyorsrendezésre Kulcs: 5
Kulcs: 1
5
3
2
6
9
1
4
7
1
3
2
4
9
6
5
7
4
3
2
6
9
1
5
7
1 3 Kulcs: 3
2
4
9
6
5
7
4
3
2
1
9
6
5
7
1
2
3
4
9
6
5
7
3
2
1
9
6
5
7
1
2
3
4
9
6
5
7
2
4
4
9
6
5
7
Kulcs: 4 4
Kulcs: 9 4
3
2
1
9
6
5
7
1
3
2
4
9
6
5
7
1 …
22
4. Kiválasztó rendezések 4.1. Rendezés közvetlen kiválasztással • Első elem a kulcs. • Keressük meg tőle jobbra a legkisebb elemet, és cseréljük meg ⇒ első rendezett • Második elem a kulcs,…
7
21
2
7
11 19 30 21
7
21
2
7
11 19 30 21
19 11 30 21
2
7
11 19 21 30
11 30 19 2 2
2
30 19 11 7
23
5. Összefésülő rendezések • Már rendezett tömböket vagy állományokat rendeznek össze úgy, hogy az egyesített részek rendezettek legyenek. • Ha csak bizonyos részek rendezettek, akkor az összerendezés után a rendezett rész hossza növekszik. • Típusai – Közvetlen összefésülés – Kétirányú összefésülő rendezés
24
5. Összefésülő rendezések 5.1. Közvetlen összefésülés Legyen A[1..n] és B[1..m] rendezett tömbök. Rendezzük össze egy C[1..n+m] tömbbe. 1.
Hasonlítsuk össze a tömbök első elemeit, a kisebbet másoljuk át egy C tömbbe.
2.
Tekintsük az elvett elem tömbjének következő elemét és hasonlítsuk össze a másik tömb aktuális elemével. A kisebbet másoljuk át a C tömbbe.
3.
A 2. lépést folytatjuk mindaddig, míg az egyik tömb elemei el nem fogynak, ekkor a másik tömb elemeit sorban átmásoljuk C-be. 25
Példa közvetlen összefésülésre A
3
6
9
B
1
2
5
8
C
1
2
3
5
11 17 19
6
8
9
11 17 19
26
