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
Powered by Facebook Comments