Tartalom Keresés és rendezés. Vektoralgoritmusok. 1. fejezet. Keresés adatvektorban. A programozás alapjai I

Keresés

Rendezés

Feladat

Keresés

Rendezés

Feladat

Tartalom Keresés és rendezés A programozás alapjai I.

1

Közvetlen kiválasztás

Keresés adatvektorban

Közvetlen beszúrás

Lineáris keresés

Buborékrendezés

Logaritmikus keresés 2

Hálózati Rendszerek és Szolgáltatások Tanszék

Összevetés Indextömbök

Rendezés Bevezetés

Farkas Balázs, Fiala Péter, Vitéz András, Zsóka Zoltán

3

Feladat

2016. november 7.

©

Farkas B., Fiala P., Vitéz A., Zsóka Z.

Keresés

Rendezés

Keresés és rendezés

Feladat

Lineáris

2016. november 7.

1 / 25

©

Logaritmikus


Keresés

Rendezés


Feladat

Lineáris

2016. november 7.

2 / 25

Logaritmikus

Vektoralgoritmusok

Emlékeztet®: eldöntési feladat

1. fejezet

Van-e a vektornak olyan eleme, amely rendelkezik egy adott tulajdonsággal?

Keresés adatvektorban Keresési feladat Van-e a vektornak olyan eleme, amely rendelkezik egy adott tulajdonsággal? Ha van, melyik az els® ilyen? tulajdonság: a tárolt elem valamelyik része (a keresés kulcsa) megegyezik egy konkrét értékkel.

©



2016. november 7.

3 / 25

©



2016. november 7.

4 / 25

Keresés

Rendezés

Feladat

Lineáris

Logaritmikus

Keresés

Lineáris keresés

Rendezés

Feladat

Lineáris

Logaritmikus

Keresés függvénnyel Ha függvényként valósítjuk meg

Az els® elemt®l kezdve egyesével vizsgáljuk az elemeket, amíg

milyen paramétereket adjunk át? mi legyen a visszatérési érték?

a keresett elemet meg nem találjuk, vagy ki nem derül, hogy nincs ilyen elem.

Visszaadhatjuk a megtalált elemet

A vektor elemtípusa

1

struktúra, amelynek egyik tagja a kulcs,

2

nagyon egyszer¶ esetben maga a kulcs típusa.

3 4

1

typedef int kulcs_tipus ; /* pl . cikksz á m */

5 6

2 3 4 5 6

typedef struct { kulcs_tipus kulcs ; double ar ; } tombelem ;

7 8 9

tombelem lin_keres_elem ( tombelem t [] , int n , kulcs_tipus kul ) { int i ; for ( i =0; i < n ; i ++) if ( t [ i ]. kulcs == kul ) return t [ i ]; return t [0]; /* ajjaj */ } kényelmes, de nem tudjuk, hol volt Mit adjunk vissza, ha nem találtunk megfelel®t?!

©


Keresés

Rendezés


Feladat

Lineáris

2016. november 7.

5 / 25

©


Logaritmikus

Keresés

Keresés hivatkozás visszaadásával


Rendezés

Feladat

2016. november 7.

Lineáris

6 / 25

Logaritmikus

A lineáris keresés várható lépésszáma

A függvény visszaadhatja a megtalált elem indexét 1 2 3 4 5 6 7 8 9

Fontos, hogy olyan kulcs érték, amely nincs tárolva a tömbben,

int lin_keres_ind ( tombelem t [] , int n , kulcs_tipus kul ) { int i ; for ( i =0; i < n ; i ++) if ( t [ i ]. kulcs == kul ) return i ; return n ; }

általában sokkal több létezik, mint olyan, amely tárolva van. Ha a tömb mérete

N,

2

a várható lépésszám

N.

-1 -3

3

4

-2

-5

Ha a tömb a kulcs szerint rendezett, a lépésszám csökkenthet®

N/2-re.

Az elemet indexeléssel elérhetjük.

a tárolt kulcsok megtalálásához átlagosan

Ha nem találtunk megfelel®t, visszaadhatunk

nem tárolt kulcsok keresésekor átlagosan

negatív indexet (pl. -1)

n-et,

N/2

N/2

lépés szükséges

lépés után d®l

el, hogy nincsenek meg (meghaladtuk)

ilyen index¶ elem már nincs

-5 -3 -2 -1

Visszaadhatjuk a megtalált elem címét Az elemet indirekcióval elérhetjük.

2

3

4

Ha nem találtunk megfelel®t, visszaadhatunk

©

null-pointert, ezt könny¶ tesztelni is Farkas B., Fiala P., Vitéz A., Zsóka Z.


2016. november 7.

7 / 25

©



2016. november 7.

8 / 25

Keresés

Rendezés

Feladat

Lineáris

Logaritmikus

Keresés

Keresés rendezett tömbben 1 2 3 4 5 6 7 8 9

tombelem * linrend_keres ( tombelem t [] , int n , kulcs_tipus kul ) { int i; for ( i =0; i < n ; i ++) if ( t [ i ]. kulcs >= kul ) return t + i ; return NULL ; }

1 2 3

6 7 8 9

11 12 13

ha nincs, akkor hivatkozást adhatunk vissza arra a tömbelemre, ahol lennie kéne

14 15

ez további vizsgálatot igényelhet a hívás helyén, de kés®bb még

16

jól jöhet

17

Ha a tömb rendezett, van még ennél is jobb módszer

Rendezés


Feladat

Logaritmikus

int main () { int a =1 , f =127; printf ( " Gondolj egy szamra % d es %d kozott !\ n " ,a , f );

5

vissza az elemre

Keresés

Lineáris

4

ha megvan a keresett kulcsú elem, akkor hivatkozást adhatunk


Feladat

Egy régi ismer®s feladat

10

©

Rendezés

Lineáris

2016. november 7.

9 / 25

©

Logaritmikus

}

while (1) { int v , k = ( a + f )/2; printf ( " % d ?\ t " , k ); scanf ( " % d " , & v ); if ( v ==0) break ; if (v >0) a = k +1; else f =k -1; } return 0;

Számkitaláló játék adott intervallumon... Farkas B., Fiala P., Vitéz A., Zsóka Z.

Keresés

Rendezés


Feladat

Bevezetés

2016. november 7.

kivál.

beszúr

buborék

összevet

10 / 25

index

Logaritmikus (bináris) keresés Ugyanígy, csak nem egy számot, hanem egy indexet keresve Minden egyes összehasonlító lépésben a keresési tartomány középs® elemét vizsgáljuk

2. fejezet

A keresési tartomány minden egyes lépésben felez®dik 1 2 3 4 5 6 7 8 9 10 11 12 13

©

14

int log_keres ( tombelem t [] , int n , kulcs_tipus kul ) { int a =0 , f =n -1 , k ; while (a < f ) { k = ( a + f )/2; if ( kul == t [ k ]. kulcs ) return k ; if ( kul > t [ k ]. kulcs ) a = k +1; else f =k -1; } return kul <= t [ k ]. kulcs ? k : k +1; }

log N

Keresés és rendezés A keresés várható lépésszáma 2


2016. november 7.

Rendezés

11 / 25

©



2016. november 7.

12 / 25

Keresés

Rendezés

Feladat

Bevezetés

kivál.

beszúr

buborék

összevet

index

Keresés

Rendezés

Rendezés

Feladat

Bevezetés

kivál.

beszúr

buborék

összevet

index

Mi kerül sokba?

Rendezni érdemes . . .

Az összehasonlítás

. . . mert rendezett N elem¶ tömbben log2 N lépésben megtalálunk egy elemet (vagy megtudjuk, hogy nincs benne) . . . mert rendezett

N

elem¶ listában

N/2

lépésben megtalálunk

egy elemet (vagy megtudjuk, hogy nincs benne) A mozgatás

Rendezni költséges . . .

13.25

. . . de tipikus, hogy ritkán rendezünk, és rengetegszer keresünk

20.10

17.30

Mibe kerül a rendezés? . . .

©

×

=

összehasonlítások száma

+

mozgatások (cserék) száma


Keresés

egy összehasonlítás költsége

×

egy mozgatás költsége


Rendezés

Feladat

Bevezetés

Nincs legjobb rendez® módszer

2016. november 7.

kivál.

beszúr

buborék

összevet

13 / 25

©

index

Keresés

Rendezés közvetlen kiválasztással Cser é ld Cser é ld Cser é ld ... Cser é ld



Rendezés

Feladat

-1

ki a 0. elemmel a t ö mb minimum á t ki az 1. elemmel az utols ó N -1 elem minimum á t ki a 2. elemmel az utols ó N -2 elem minimum á t

A tömb egy és egy

ki az N -2. elemmel az utols ó 2 elem minimum á t

0

7

2

1

5 1

MINDEN i - re 0 - t ó l N -2 - ig iMin ← i MINDEN j - re i +1 - t ®l N -1 - ig HA t [ j ] < t [ iMin ] iMin ← j ; t [ i ] ↔ t [ iMin ]; Összehasonlítások száma:

©

Cserék száma: Farkas B., Fiala P., Vitéz A., Zsóka Z.

2 3 4 5 6 7

2

O N O (N)

kivál.

beszúr

buborék

összevet

14 / 25

index


N −i

i(= 4)

hosszú rendezett szakaszból

hosszú rendezetlen szakaszból áll. 5.

-3

Bevezetés

2016. november 7.

1

3

≈ N 2 /2 N −1


2016. november 7.

15 / 25

3

4 4.

for ( i =0; i
1.

x

7 3.

2

1

5

3

2.

A rendezetlen rész els® elemét szúrjuk be a rendezett részbe, a megfelel® pozícióba Ezzel a rendezett szakasz hossza eggyel n®tt Kezdetben

©

i = 1,


az egyelem¶ tömb ugyanis rendezett


2016. november 7.

16 / 25

Keresés

Rendezés

Feladat

Bevezetés

kivál.

beszúr

buborék

összevet

index

Keresés


Rendezés

Feladat

Bevezetés

kivál.

beszúr

buborék

összevet

index

Közvetlen beszúrás A közvetlen beszúrás C-kódja

5.

1.

x

1 2

1

3

4

7

4.

2

3.

1

5

3

3

4 5

2.

6 7 8

A rendezett részben az új elem helyét log2 i lépésben megtaláljuk Összehasonlítások száma:

O (N · log2 N)

A beszúráshoz átlagosan Mozgatások száma:

9 10

i/2 O N2

11 12

elemet el kell húzni (max. (N 2 /2) mozgatás)

13 14 15

©


Keresés


Rendezés

Feladat

Bevezetés

2016. november 7.

kivál.

beszúr

buborék

összevet

17 / 25

©

Keresés

3 4

1 2

for ( iter = 0; iter < n -1; ++ iter ) for (i = 0; i < N - iter -1; ++ i ) if ( t [ i ] > t [ i +1]) xchg ( t +i , t + i +1);

3 4 5 6 7

i = 0 1

2

8

4

7

7

8

9

9

10

N-iter-1 = 1 Összehasonlítások száma: Cserék száma:

O N 2 O N2

N 2 /2

Feladat

Bevezetés

2016. november 7.

kivál.

beszúr

buborék

összevet

18 / 25

index

max.

1

(N 2 /2)


2016. november 7.

2

4

7

7

8

9

stop = 0 nextstop = 0 Az összehasonlítások száma csökkent

ki korábban?


stop = n -1; while ( stop != 0) { nextstop = 0; /* utols ó csere indexe */ for (i = 0; i < stop ; ++ i ) if ( t [ i ] > t [ i +1]) { xchg ( t +i , t + i +1) nextstop = i ; } stop = nextstop ; } i = 0

Az utolsó három körben nem cseréltünk semmit. Nem derül ez

©

Rendezés


Javított buborékrendezés cserék gyelésével

Szomszédos elemeket vizsgálunk. Ha rossz sorrendben állnak, csere 2


index

Buborékrendezés

1

for (i =1; i < N ; i ++) { s = t [ i ]; /* besz ú rand ó elem */ for (a =0 , f = i ; a < f ;) /* log keres é s 0 i k ö z ö tt */ { k = ( a +f )/2; if ( t [ k ] < s ) a = k +1; else f = k; } for (j = i ; j > a ; j - -) /* r é szt ö mb h ú z á sa */ t [ j ] = t [j -1]; t [ a ]= s ; /* besz ú r á s */ }

19 / 25

©

A cserék száma maradt Farkas B., Fiala P., Vitéz A., Zsóka Z.


2016. november 7.

20 / 25

Keresés

Rendezés

Feladat

Bevezetés

kivál.

beszúr

buborék

összevet

index

Keresés

Rendez® algoritmusok összehasonlítása

Rendezés

Feladat

Bevezetés

kivál.

beszúr

buborék

összevet

index

Indextömbök Az adatmozgatások száma jelent®sen csökkenthet®, ha nem a

N = 100 000

összehasonlítások

közvetlen kiválasztás

tömbelemeket, hanem azok indexeit rendezzük

mozgatások száma

4 999 950 000

299 997

1 522 642

2 499 618 992

0

ABC123

Aladár

0

0

1

QE8BZX

Dzsenifer

1

6

2

S45FDO

Kristóf

2

3

KJ967F

Gyöngyvér

3

4

FEK671

Éva

4

3

5

F34K98

Mihály

5

2

6

D678EF

Berci

6

5

közvetlen beszúrás buborék

4 999 950 000

7 504 295 712

javított buborék

4 999 097 550

7 504 295 712

3 147 663

1 295 967

gyorsrendezés

összehasonlító program

1 2

−→

1 4

név szerint rendez® indextömb

eredeti adatvektor

Nincs legjobb algoritmus1 .

rendezés

for (i = 0; i < n ; ++ i ) /* n é vsor */ printf ( " % s \ n " , data [ index [ i ]]. name ); Indexek helyett rendezhetünk mutatókat is, ha az eredeti tömb

©

1

(vagy lista) a memóriában van csak legrosszabb


Keresés

Rendezés


Feladat

Bevezetés

2016. november 7.

kivál.

beszúr

buborék

összevet

21 / 25

©

index


Keresés

Rendezés


2016. november 7.

22 / 25

2016. november 7.

24 / 25

Feladat

Rendezés több szempont szerint

Több kulcs szerint rendezés indextömbökkel

3. fejezet

Gyors keresés érdekében érdemes az indextömbökben a kulcsokat is tárolni, és az indextömböket kulcs szerint rendezve tartani

©

0

ABC123

Aladár

Aladár

0

ABC123

0

1

QE8BZX

Dzsenifer

Berci

6

D678EF

6

2

S45FDO

Kristóf

Dzsenifer

1

FEK671

4

3

KJ967F

Gyöngyvér

Éva

4

F34K98

5

4

FEK671

Éva

Gyöngyvér

3

KJ967F

3

5

F34K98

Mihály

Kristóf

2

QE8BZX

1

6

D678EF

Berci

Mihály

5

S45FDO

2



2016. november 7.

Feladat

23 / 25

©



Keresés

Rendezés

Feladat

Egy összetettebb feladat

Írjunk programot, mely egy szöveges fájl összes max. 50 bet¶s szavának gyakoriságáról statisztikát készít Tervezés Szavak száma csak menet közben derül ki

→

láncolt lista

Gyorsabb keresés miatt névsor szerint rendezett Rendezett beszúrások miatt elöl strázsás

©



2016. november 7.

25 / 25

Tartalom Keresés és rendezés. Vektoralgoritmusok. 1. fejezet. Keresés adatvektorban. A programozás alapjai I

Recommend Documents