18. Oszd meg és uralkodj elvű algoritmusok

Oszd meg és uralkodj elv:

A Merge és Quickshort rendezések Oszd meg és uralkodj elven működnek.

Elv:

• A megoldandó problémát felosztjuk kisebb részfeladatokra
• Az egyes részfeladatokat rekurzív módon megoldjuk
• A részfeladatok megoldásait egyesítjük

Ezzel a megközelítéssel olyan problémák is megoldhatóak, amiket más módszerrel is meg lehet oldani.

Maximumkiválasztás:

Pszeudokód(Bemenet: X-tömb, N – X elemszáma Kimenet: X elemainek maximuma):

Függvény FelezőMaximumkiválasztás(X,N)

Ha N=1 akkor

return(X[1])

különben

K<- egészrész(N/2)

BalMac<- FelezőMaximumkiválasztás(X[1..K],K)

JobbMax<-FelezőMaximumkiválasztás(X[K+1..N], N-K)

Ha BalMax>=JobbMax akkor

return(BalMax)

különben

return(jobbMax)

Elágazás vége

Elágazás vége

Függvény vége

K-adik legkisebb elem meghatározása:

Pszeudokód(X: tömb, E: első elem a tömbben, U: utolsó elem a tömbben, k: ennyiedik legkisebb elemet keressük):

Függvény KiválasztK_adik(X,E,U,k)

Ha E=U akkor

return(X[E])

elágazás vége

Szétválogat(X,E,U,K)

Elágazás

k=K esetén

return X[K]

k<K esetén

KiválasztK_adik(X,E,K-1,k)

k>K esetén

KiválasztK_adik(X,K+1,U,k-K)

Elágazás vége

Függvény vége

• A fent bemutatott algoritmussal átlagos esetben O(N)-es, de legrosszabb esetben O(NlogN)-es
• Ha még javítani szeretnénk a futási időn akkor át kell gondolnunk, hogy hogyan válasszuk meg a viszonyítási elemet(örszem)

A Quicksort algoritmus őrszem elemének kiválasztása:

• A bemeneti tömb n darab elemét bontsuk egészrész(N/5) darab 5 elemből álló csoportra. A maradék n mod 5 elemből alkossunk egy újabb csoportot, ha n mod 5 != 0.
• Az egészrész(n/5) darab csoportnak keressük meg a mediánját. Ez esetben ez a 3. legkisebb elem. Ehhez rendezzük az 5 darab elemet javított beillesztéses rendezéssel, majd minden csoportból válasszuk ki a mediánt.
• A KiválasztK_adik függvény rekurzív használatával határozzuk meg az előző lépésben kapott egészrész(N/5) darab medián x-szel jelölt mediánját.
• A szétválogatásnál pedig x-et használjuk őrszem elemként!

Felhasznált Irodalom: Sergyán Szabolcs – Programozás I – 10. előadás diasor

Kommentek

comments

Powered by Facebook Comments