Egyszerű programozási tételek Sorozatszámítás Eljárás Sorozatszámítás(N, X, S) R ← R0 Ciklus i ← 1-től N-ig R ← R művelet A[i] Ciklus vége Eljárás vége
Bemenet: A : számokat tartalmazó tömb N : A tömb elemszáma Kimenet: R : Művelet eredménye
Eldöntés Eljárás Eldöntés(A, N, T, VAN) i←1 Ciklus amíg(i ≤ N) és ¬T (A[i]) i←i+1 Ciklus vége VAN ← (i ≤ N) Eljárás vége
Bemenet: A : Feldolgozandó tömg N : Tömb elemeinek száma T : Tulajdonság függvény Kimenet: VAN : logikai változó
Kiválasztás Eljárás Kiválasztás(A, N, T, SORSZ) i←1 Ciklus amíg ¬T (A[i]) i←i+1 Ciklus vége SORSZ ← i Eljárás Vége
Bemenet: A : feldolgozandó tömb N : Tömb elemeinek száma T : tulajdonság függvény Kimenet: SORSZ : az első T tulajdonságú elem indexe
Lineáris Keresés Eljárás Keresés(A, N, T, VAN, SORSZ) i←1 Ciklus amíg(i ≤ N) és ¬T(A[i]) i←i+1 Ciklus vége VAN ← ( i ≤ N) Ha VAN akkor SORSZ ← i Elágazás vége Eljárás vége
Bemenet: A : Feldolgozandó tömb N : Tömb elemeinek száma T : tulajdonság függvény Kimenet: VAN : Logikai változó SORSZ : első T tulajdonságú elem indexe
Megszámlálás Eljárás Megszámlálás(A, N, T, DB) DB ← 0 i←1 Ciklus i ← 1-től N-ig Ha T(A[i]) akkor DB ← DB + 1 Elágazás vége Ciklus vége Eljárás Vége
Bemenet: A : feldolgozandó tömb N : Tömb elemeinek száma T : tulajdonság függvény Kimenet: DB : T tulajdonságú elemek száma
Maximumkiválasztás Eljárás Maximumkiválasztás(A, N, MAX) MAX ← 1 Ciklus i ← 2-től N-ig Ha A[i] > A[MAX] akkor MAX ← i Elágazás vége Ciklus vége Eljárás vége
Bemenet: A : Feldolgozandó tömb N : tömb elemeinek száma Kimenet: MAX : maximális elme indexe
Másolás Eljárás Másolás(X, N, Y) Ciklus i ← 1-től N-ig Y[i] ← művelet X[i] Ciklus vége Eljárás vége
Bemenet: X : Feldolgozandó tömb N : tömb elemeinek száma Kimenet: Y : Eredmény tömb
Kiválogatás Eljárás Kiválogatás(X, N, T, Y, DB) DB ← 0 Ciklus i ← 1-től N-ig Ha T(X[i]) akkor DB ← DB + 1 Y[DB] ← X[i] Elágazás vége Ciklus vége Eljárás vége
Bemenet: X : Feldolgozandó tömb N : Tömb elemeinek száma T : Tulajdonság függvény Kimenet: Y : eredmény tömb DB : Y tömbbe kiválogatott elemek száma
Szétválogatás Eljárás Szétválogatás(X, N, T, Y, DBY, Z, DBZ) DBY ← 0 DBZ ← 0 Ciklus i ← 1-től N-ig Ha T(X[i]) akkor DBY ← DBY + 1 Y[DBY] ← X[i] Különben DBZ ← DBZ + 1 Z[DBZ] ← X[i] Elágazás vége Ciklus vége Eljárás vége
Bemenet: X : Feldolgozandó tömb N : Tömb elemeinek száma T : Tulajdonság függvény Kimenet: Y : egyik eredmény tömb DBY : X T tulajdonságú elemeinek száma Z : másik eredmény tömb DBZ : X ¬T tulajdonságú elemeinek száma
Szétválogatás egyetlen tömbbe Eljárás Szétválogatás(X, N, T, Y, DBY) DBY ← 0 INDZ ← N + 1 Ciklus i ← 1-től N-ig Ha T(X[i]) akkor DBY ← DBY + 1 Y[DBY] ← X[i] Különben INDZ ← INDZ – 1 Y[INDZ] ← X[i] Elágazás vége Ciklus vége Eljárás vége
Metszet Eljárás Metszet(X, M, Y, N, Z, DB) DB ← 0 Ciklus i ← 1-től M-ig j←1 Ciklus amíg j ≤ N és X[i] ≠ Y[j] j←j+1 Ciklus vége Ha j ≤ N akkor DB ← DB + 1; Z[DB] ← X[i] Elágazás vége Ciklus vége Eljárás vége
Bemenet: X : Egyik feldolgozandó tömb M : X elemeinek száma Y : másik feldolgozandó tömb N : Y elemeinek száma Kimenet: Z : Eredmény tömb DB : Metszetbeli elemek száma
Szétválogatás a bemeneti tömbben Eljárás Szétválogatás(X, N, T, DB) E ← 1; U ← N; seged ← X[E] Ciklus amíg E < U Ciklu amíg E < U és ¬(T(X[U])) U ← U -1 Ciklus vége Ha E < U akkor X[E] ← X[U]; E ← E + 1; Ciklus amíg E < U és T(X[E]) E←E+1 Ciklus vége Ha E < U akkor X[U] ← X[E]; U ← U – 1 Elágazás vége Elágazás vége Ciklus vége X[E] ← seged Ha T(X[E]) akkor DB ← E Különben DB ← E - 1 Elágazás vége Eljárás vége
Közös elem keresése Eljárás MetszetbeliElem(X, M, Y, N, VAN, E) i ← 1; VAN ← hamis Ciklus amíg i ≤ M és ¬VAN j←1 Ciklus amíg j ≤ N és X[i] ≠ Y[j] j←j+1 Ciklus vége Ha j ≤ N akkor VAN ← igaz; E ← X[i] Különben i←i+1 Elágazás vége Ciklus vége Eljárás vége
Bemenet: X : egyik tömb M : X elemeinek száma Y : másik tömb elemeinek száma N : Y elemeinek száma Kimenet: VAN : logikai változó, pontosan akkor igaz ha a két tömbben van közös elem E : a közös elem értéke (ha van)
Egyesítés Eljárás Egyesítés(X, M, Y, N, Z, DB) Z ← X; DB ← M Ciklus j ← 1-től N-ig i←1 Ciklus amíg i ≤ M és X[i] ≠ Y[j] i←i+1 Ciklus vége Ha i > M akkor DB ← DB + 1; Z[DB] ← Y[j] Elágazás vége Ciklus vége Eljárás vége
Bemenet: X : egyik bemenet M : X elemeinek száma Y : másik bemenet N : Y elemeinek száma Kimenet: Z : eredmény tömb DB : Unióbeli elemek száma
Halmazfelsorolás készítés Eljárás HalmazfelsorolásKészítés(X, N, Z, DB) DB ← 0 Ciklus i ← 1-től N-ig j←1 Ciklus amíg j ≤ DB és X[i] ≠ Z[j] j←j+1 Ciklus vége Ha j > DB akkor DB ← DB + 1 Z[DB] ← X[i] Elágazás vége Ciklus vége Eljárás vége
Összefuttatás Eljárás Összefuttatás(X, M, Y, N, Z, DB) i ← 1 j ← 1; DB ← 0 Ciklus amíg i ≤ M és j ≤ N DB ← DB + 1 Elágazás X[i] < Y[j] esetén Z[DB] ← X[i]; i ← i + 1 X[i] = Y[j] esetén Z[DB] ← X[i]; i ← i + 1; j ← j + 1 X[i] > Y[j] esetén Z[DB] ← Y[j]; j ← j + 1 Elágazás vége Ciklus vége Ciklus amíg i ≤ M DB ← DB + 1; Z[DB] ← X[i]; i ← i + 1 Ciklus vége Ciklus amíg j ≤ N DB ← DB + 1; Z[DB] ← Y[j]; j ← j + 1 Ciklus vége Eljárás vége
Bemenet: X : eredeti sorozat N : X elemeinek száma Kimenet: Z : halmazzá alakított sorozat DB : Z elemeinek száma
Összefuttatás (redezettek úniója) Ha X[M] = Y[N], akkor az utolsó két ciklusra nincs szükség. Ezt a helyzetet magunk is előidézhetjük. Eljárás Összefuttatás(X, M, Y, N, Z, DB) i ← 1; j ← 1; DB ← 0 X[M + 1] ← +∞; Y[N + 1] ← +∞ Ciklus amíg i < M + 1 vagy j < N + 1 DB ← DB + 1 Elágazás X[i] < Y[j] esetén Z[DB] ← X[i]; i ← i + 1 X[i] = Y[j] esetén Z[DB] ← X[i]; i ← i + 1; j ← j + 1 X[i] > Y[j] esetén Z[DB] ← Y[j]; j ← j + 1 Elágazás vége Ciklus vége Eljárás vége
Ha nincs a két sorozatban azonos elem, akkor a megvalósítás még egyszerűbb Eljárás Összefuttatás(X, M, Y, N, Z, DB) i ← 1; j ← 1; DB ← 0 X[M +1] ← +∞; Y[N + 1] ← +∞ Ciklus amíg i < M + 1 vagy j < N + 1 DB ← DB + 1 Ha X[i] < Y[j] akkor Z[DB] ← X[i]; i ← i + 1 Különben Z[DB] ← Y[j]; j ← j + 1 Elágazás vége Ciklus vége Eljárás vége
Algoritmusok összeépítése Másolás és sorozatszámítás összeépítése Eljárás Másolás_Sorozatszámítás(X, N, R) R ← R0 Ciklus i ← 1-től N-ig R ← R művelet g(X[i]) Ciklus vége Eljárás vége
Bemenet: X : Feldolgozandó tömb N : Tömb elemeinek száma Kimenet: R : Művelet eredménye
Másolás és maximumkiválasztás összeépítése Eljárás Másolás_Maximumkiválasztás(N, X, MAX, MAXERT) MAX ← 1 MAXERT ← g(X[1]) Ciklus i ← 2-től N-ig Ha MAXERT < g(X[i]) akkor MAXERT ← g(X[i]) MAX ← i Elágazás vége Ciklus vége Eljárás vége
Bemenet: X : Feldolgozandó tömb N: Tömb elemeinek száma Kimenet: MAX : Maximális értékű elem indexe MAXERT: Maximális érték
Megszámolás és keresés összeépítése Eljárás Megszámolás_Keresés(N, X, T, K, VAN, SORSZ) i ← 0; DB ← 0 Ciklus amíg (i < N) és (DB < K) i←i+1 Ha T(X[i]) akkor DB ← DB + 1 Elágazás vége Ciklus vége VAN ← (DB = K) Ha VAN akkor SORSZ ← i Elágazás vége Eljárás vége
Bemenet: X : Feldolgozandó tömb N : Tömb elemeinek száma T : tulajdonság függvény K : A K-adik T tulajdonságú elemet keressük Kimenet: VAN : Logikai változó SORSZ : A K-adik T tulajdonságú elem indexe
Maximumkiválasztás és kiválogatás összeépítése Eljárás Maximumkiválogatás(X, N, DB, Y, MAXERT) MAXERT ← X[1] DB ← 1 Y[DB] ←1 Ciklus i ← 2-től N-ig Elágazás X[i] > MAXERT esetén MAXERT ← X[i] DB ← 1 Y[DB] ← i X[i] = MAXERT esetén DB ← DB + 1 Y[DB] ← i Elágazás vége Ciklus vége Eljárás vége
Bemenet: X : Feldolgozandó tömb N : Tömb elemeinke száma Kimenet DB : Maximális elemek száma Y : Maximális elemek indexei MAXERT : Maximális érték
Kiválogatás és sorozatszámítás összeépítése Eljárás Kiválogatás_Sorozatszámítás(X, N, T, R) R ← R0 Ciklus i ← 1-től N-ig Ha T(X[i]) akkor R ← R művelet X[i] Elágazás vége Ciklus vége Eljárás vége
Bemenet: X : feldolgozandó tömb N : Tömb elemeinek száma T : Tulajdonság függvény Kimenet: R : Művelet eredménye
Kiválogatás és Maximumkiválasztás összeépítése Eljárás Kiválogatás_Maximumkiválasztás(X, N, T, VAN, MAX, MAXERT) MAXERT ← -∞ Ciklus i ← 1-től N-ig Ha T(X[i]) és X[i] > MAXERT akkor MAXERT ← X[i] MAX ← i Elágazás vége Ciklus vége VAN ← (MAXERT ≠ -∞) Eljárás vége
Bemenet: X : feldolgozandó tömb N : Tömb elemeinek száma T : Tulajdonság függvény Kimenet: VAN : Logikai változó MAX : A maximális értékű elem indexe MAXERT : A maximális érték
Kiválogatás és Másolás összeépítése Eljárás Kiválogatás_Másolás(X, N, T, f, DB, Z) DB ← 0 Ciklus i ← 1-től N-ig Ha T(X[i]) akkor DB ← DB + 1 Z[DB] ← f(X[i]) Elágazás vége Ciklus vége Eljárás vége
Bemenet: X : feldolgozandó tömb N : Tömb elemeinek száma T : Tulajdonság függvény f : Végrehajtandó függvény Kimenet: DB : T tulajdonságú elemek száma Z : Feldolgozott sorozat
Rendezések Egyszerű cserés rendezés Eljárás Rendezés(N, X) Ciklus i ← 1-től N - 1-ig Ciklus j ← i + 1-től N-ig Ha X[i] > X[j] akkor Csere(X[i], X[j]) Elágazás vége Ciklus vége Ciklus vége Eljárás vége
Hatékonyság Helyfoglalás: N + 1 Hasonlítások száma: N(N-1) / 2 Mozgatások száma: legalább 0, legfeljebb 3 * N(N – 1) / 2
Csere megvalósítása Eljárás Csere(X[i], X[j]) TEMP ← X[i] X[i] ← X[j] X[j] ← TEMP Eljárás vége
Minimumkiválasztásos rendezés Eljárás Rendezés(N, X) Ciklus i ← 1-től N – 1-ig MIN ← i Ciklus j ← i + 1-től N-ig Ha X[MIN] > X[j] akkor MIN ← j Elágazás vége Ciklus vége Csere (X[i], X[MIN]) Ciklus vége Eljárás vége
Hatékonyság Helyfoglalás: N + 1 Hasonlítások száma: N(N - 1) / 2 Mozgatások száma: 3 * (N – 1)
Buborékos rendezés Eljárás Rendezés(N, X) Ciklus i ← N-től 2-ig -1-esével Ciklus j ← 1-től i - 1-ig Ha X[j] > X[j + 1] akkor Csere(X[j], X[j + 1]) Elágazás vége Ciklus vége Ciklus vége Eljárás vége
Hatékonyság Helyfoglalás: N + 1 Hasonlítások száma: N(N - 1) / 2 Mozgatások száma: legalább 0, legfeljebb 3 * N(N – 1) / 2
Javított buborékos rendezés
Hatékonyság
Eljárás Rendezés(N, X) i←N Ciklus amíg i ≥ 2 CS ← 0 Ciklus j ← 1-től i – 1-ig Ha X[j] > X[j + 1] akkor Csere(X[j], X[j + 1] CS ← j Elágazás vége Ciklus vége i ← CS Ciklus vége Eljárás vége
Helyfoglalás: N + 1 Hasonlítások száma: legalább: N – 1 legfeljebb: N(N - 1) / 2 Mozgatások száma: legalább 0, legfeljebb 3 * N(N – 1) / 2
Beillesztéses rendezés Eljárás Rendezés(N, X) Ciklus i ← 2-től N-ig j←i–1 Ciklus amíg j > 0 és X[j] > X[j + 1] Csere (X[j], X[j + 1]) j←j–1 Ciklus vége Ciklus vége Eljárás vége
Hatékonyság Helyfoglalás: N + 1 Hasonlítások száma: legalább: N – 1 legfeljebb: N(N - 1) / 2 Mozgatások száma: legalább 0, legfeljebb 3 * N(N – 1) / 2
Javított Beillesztéses rendezés Eljárás Rendezés(N, X) Ciklus i ← 2-től N-ig j←i–1 Y ← X[i] Ciklus amíg j > 0 és X[j] > Y X[j + 1] ← X[j] j←j–1 Ciklus vége X[j + 1] ← Y Ciklus vége Eljárás vége
Hatékonyság Helyfoglalás: N + 1 Hasonlítások száma: legalább: N – 1 legfeljebb: N(N - 1) / 2 Mozgatások száma: legalább 2 * (N - 1) legfeljebb 2 * (N – 1) + N(N – 1) / 2
Rendezés Shell módszerrel Eljárás rendezés(N, X) L ← L0 Ciklus amíg L ≥ 1 Ciklus K ← L + 1-től 2L-ig Ciklus i ← K-tól N-ig L-esével j←i–L Y ← X[i] Ciklus amíg j ≥ 0 és X[j] > Y X[j + L] ← X[j] j←j–L Ciklus vége X[j + L] ← Y Ciklus vége Ciklus vége L ← Következő(L) Ciklus vége Eljárás vége
Rendezés Shell módszerrel módosított Eljárás Rendezés(N, X) L ← L0 Ciklus amíg L ≥ 1 Ciklus i ← L + 1-től N-ig j←i–L Y ← X[i] Ciklus amíg j > 0 és X[j] > Y X[j + L] ← X[j] j←j–L Ciklus vége X[j + L] ← Y Ciklus vége L ← Következő(L) Ciklus vége Eljárás vége
Rekurzív algoritmusok Faktoriális Függvény fakt(N) Ha N = 0, akkor return(1) Különben return(N * fakt(N - 1)) Elágazás vége Függvény vége
Fibonacci Függvény Fib(N) Ha N ≤ 1 akkor return(1) Különben return(Fib(N – 1) + Fib(N - 2)) Elágazás vége Függvény vége
Binomális együtthatók Függvény Bin(N, K) Ha (K = 0) vagy (K = N) akkor return(1) Különben return(Bin(N – 1, K) + Bin(N – 1, K – 1)) Elágazás vége Eljárás vége
Szöveg megfordítás Függvény Fordítás(X, N) Ha N > 1 akkor return(Fordítás(X[2..N], N – 1) + X[1]) Elágazás vége Függvény vége
Palindrom Függvény Palindrom_e(X, N) Ha N ≤ 1 akkor return(Igaz) Különben Ha X[1] = X[N] akkor return(Palindrom_e(X[2..N – 1], N - 2)) Különben return(Hamis) Elágazás vége Elágazás vége Függvény vége
Hatványozás Függvény Hatvány(a, n) Ha n = 0 akkor return(1) Különben Ha n páros, akkor return(Hatvány(a, n/2)* Hatvány(a, n/2)) Különben return(Hatvány(a, (n - 1)/2) * Hatvány(a, (n - 1)/2) * a) Elágazás vége Elágazás vége Függvény vége
Hanoi tornyai Eljárás Hanoi(N, Forras, Cel, Seged) Ha N > 0 akkor Hanoi(N – 1, Forras, Seged, Cel) Ki: N, Forras, Cel Hanoi(N – 1, Seged, Cel, Forras) Elágazás vége Eljárás vége
Programozási tételek rekurzív megvalósítása Sorozatszámítás Függvény Sorozatszámítás(A, N) Ha N = 0 akkor return(R0) Különben return(A[N] művelet Sorozatszámítás(A[1..N - 1],N - 1)) Elágazás vége Függvény vége
Megszámlálás Függvény Megszámlálás(A, N, T) Ha N = 1 akkor Ha T(A[N]) akkor return(1) Különben return(0) Elágazás vége Különben Ha T(A[N]) akkor return(1 + Megszámlálás(A, N - 1, T)) Különben return(Megszálálás(A, N - 1, T)) Elágazás vége Elágazás vége Függvény vége
Maximumkiválasztás Függvény Maximumkiválasztás(A, N) Ha N = 1 akkor return(N) Különben eddigiMax ← Maximumkiválasztás(A, N – 1) Ha A[N] > A[eddigiMax] akkor return(N) Különben return(eddigiMax) Elágazás vége Elágazás vége Függvény vége
Lineáris keresés Függvény Keresés(X, E, U, Y) Ha E > U akkor return(0) Különben Ha X[E] = Y akkor return(E) Különben return(Keresés(X, E + 1, U, Y) Elágazás vége Elágazás vége Függvény vége
Keresések, halmazok, halmazműveletek Lineáris keresés Eljárás LineárisKeresés(X, N, Y, VAN, SORSZ) i←1 Ciklus amíg (i ≤ N) és X[i] ≠ Y) i←i+1 Ciklus vége VAN ← (i ≤ N) Ha VAN akkor SORSZ ← i Elágazás vége Eljárás vége
-Minimális lépésszám: 1 -Maximális lépésszám: N (Ezt kapjuk minden olyan esetben is, ha Y nincs benne a sorozatban!) -Az átlagos futási idő: O(N) -Ezért hívjuk lineáris keresésnek
Lineáris keresés (rekurziv megvalósítás) Függvény Keresés(X, E, U, Y) Ha E > U akkor return(0) Különben Ha X[E] = Y akkor return(E) Különben return(Keresés(X, E + 1, U, Y) Elágazás vége Elágazás vége Függvény vége
Keresés rendezett sorozatban Eljárás LineárisKeresés(X, N, Y, VAN, SORSZ) i←1 Ciklus amíg (i ≤ N) és (X[i] < Y) i←i+1 Ciklus vége VAN ← (i ≤ N) és (X[i] = Y) Ha VAN akkor SORSZ ← i Elágazás vége Eljárás vége
-Minimális lépésszám: (Akkor is előállhat ez ha Y nincs benne a sorozatban!) -Maximális lépésszám: N -Átlagos lépésszám: (Nem függ attól, hogy Y benne van-e a sorozatban!)
Logaritmikus keresés Függvény Keresés(X, E, U, Y) Ha E > U akkor return(0) Különben K ← [ (E + U)/2 ] Elágazás X[K] = Y esetén return(K) X[K] < Y esetén return(Keresés(X, K + 1, U, Y) X[K] > Y esetén return(Keresés(X, E, K – 1, Y) Elágazás vége Elágazás vége Függvény vége
[ ] az egészrész függvényt jelöli Logaritmikus keresés Iteratív megoldás Eljárás LogaritmikusKeresés(X, N, Y, VAN, SORSZ) E ← 1; U ← N Ciklus K ← [ (E + U)/2 ] Elágazás Y < X[K] esetén U←K–1 Y > X[K] esetén E←K+1 Elágazás vége Amíg (E ≤ U) és (X[K] ≠ Y) VAN ← (E ≤ U) Ha VAN akkor SORSZ ← K Elágazás vége Eljárás vége
[ ] az egészrész függvényt jelöli
-Minimális lépésszám: 1 (ha a középső elem az Y) -Maximális lépésszám: [1 + log2N] -Átlagos lépésszám: [log2N] -Így már érthető, honnan kapta a nevét az eljárás -Van, aki felezéses- vagy bináris keresésnek hívja az eljárást az alapütlet miatt.
[ ] az egészrész függvényt jelöli
Eldöntés felezéses módszerrel Eljárás Eldöntés(X, N, Y, VAN) E ← 1; U ← N Ciklus K ← [ (E + U)/2 ] Elágazás Y < X[K] esetén U←K–1 Y > X[K] esetén E←K+1 Elágazás vége Amíg (E ≤ U) és (X[K] ≠ Y) VAN ← (E ≤ U) Eljárás vége
Kiválasztás felezéses módszerrel Eljárás Kiválasztás(X, N, Y, SORSZ) E ← 1; U ← N Ciklus K ← [ (E + U)/2 ] Elágazás Y < X[K] esetén U←K–1 Y > X[K] esetén E←K+1 Elágazás vége Amíg(E ≤ U) és (X[K] ≠ Y) SORSZ ← K Eljárás vége
Kiválogatás felezéses módszerrel Eljárás Kiválogatás(X, N, Y, VAN, E, U) E ← 1; U ← N Ciklus K ← [ (E + U)/2 ] Elágazás Y < X[K] esetén U←K–1 Y > X[K] esetén E←K+1 Elágazás vége Amíg (E ≤ U) és (X[K] ≠ Y) VAN ← (E ≤ U) Ha VAN akkor E←K Ciklus amíg (E > 1) és (X[E – 1] = Y) E←E–1 Ciklus vége U←K Ciklus amíg (U < N) és (X[U + 1] =Y) U←U+1 Ciklus vége Elágazás vége Eljárás vége Halmaz: halmaznak tekintünk egy olyan (növekvő módon) rendezett tömböt, melynek minden eleme különböző.
Halmaz létrehozása Eljárás HalmazLétrehozás(X, N, M) j←1 Ciklus i ← 1-től N-ig Ha X[i] ≠ X[j] akkor j←j+1 X[j] ← X[i] Elágazás vége Ciklus vége M←j Eljárás vége
Bemenet: N elemű rendezett tömb (X) Kimenet: M elemű halmaz (X)
Halmaz-e? Eljárás Halmaz_e(N, X, L) i←2 Ciklus amíg (i ≤ N) és (X[i] ≠ X[i – 1]) i←i+1 Ciklus vége L ← (i > N) Eljárás vége
Bemenet: N (legalább kettő) elemű rendezett tömb Kimenet: L logikai változó
Tartalmazás A logaritmikus keresésből származtatott Eldöntést kell alkalmazni. Eljárás Eldöntés(X, N, Y, VAN) E ← 1; U ← N Ciklus K ← [ (E + U)/2 ] Elágazás Y < X[K] esetén U←K–1 Y > X[K] esetén E←K+1 Elágazás vége Amíg (E ≤ U) és (X[K] ≠ Y) VAN ← (E ≤ U) Eljárás vége
Részhalmaz A
B, ha A minden eleme a B-nek is eleme.
Eljárás Részhalmaz(X, M, Y, N, L) i ← 1; j ← 1 Ciklus amíg (i ≤ M) és (j ≤ N) és (X[i] ≥ Y[j]) Ha X[i] = Y[j] akkor i←i+1 Elágazás vége j←j+1 Ciklus vége L ← (i > M) Eljárás vége
Unió A U B = {x|x
A vagy x
B}
Eljárás Összefuttatás(X, M, Y, N, DB, Z) i ← 1; j ← 1; DB ← 0 X[M + 1] ← +∞; Y[N + 1] ← +∞ Ciklus amíg (i < M + 1) vagy (j < N + 1) DB ← DB + 1 Elágazás X[i] < Y[j] esetén Z[DB] ← X[i]; i ← i + 1 X[i] = Y[j] esetén Z[DB] ← X[i]; i ← i + 1; j ← j + 1 X[i] > Y[j] esetén Z[DB] ← Y[j]; j ← j + 1 Elágazás vége Ciklus vége
Eljárás vége
Metszet A
B = x|x
A és x
B}
Eljárás Metszet(X, M, Y, N, DB, Z) i ← 1; j ← 1; DB ← 0 Ciklus amíg (i ≤ M) és j ≤ N) Elágazás X[i] < Y[j] esetén i←i+1 X[i] > Y[j] esetén j←j+1 X[i] = Y[j] esetén DB ← DB + 1 Z[DB] ← X[i] i ← i + 1; j ← j + 1 Elágazás vége Ciklus vége Eljárás vége
Különbség A \ B = {x|x
A és x
B}
Eljárás különbség(X, M, Y, N, DB, Z) i ← 1; j ← 1; DB ← 0 Ciklus amíg (i ≤ M) és (j ≤ N) Elágazás X[i] < Y[j] esetén DB ← DB + 1 Z[DB] ← X[i] i←i+1 X[i] > Y[j] esetén j←j+1 X[i] = Y[j] esetén i ← i + 1; j ← j + 1 Elágazás vége Ciklus vége Ciklus amíg (i ≤ M) DB ← DB + 1; Z[DB] ← X[i]; i ← i + 1 Ciklus amíg Eljárás vége
Szimmetrikus differencia A
B = (A\B)
(B\A)
Eljárás SzimmetrikusDifferencia(X, M, Y, N, DB, Z) i ← 1; j ← 1; DB ← 0 Ciklus amíg (i ≤ M) és (j ≤ N) Elágazás X[i] < Y[j] esetén DB ← DB + 1 Z[DB] ← X[i] i←i+1 X[i] > Y[j] esetén DB ← DB + 1 Z[DB] ← Y[j] j←j+1 X[i] = Y[j] esetén i ← i + 1; j ← j + 1 Elágazás vége Ciklus vége Ciklus amíg (i ≤ M) DB ← DB + 1; Z[DB] ← X[i]; i ← i + 1 Ciklus vége Ciklus amíg (j ≤ N) DB ← DB + 1; Z[DB] ← Y[j]; j ← j + 1 Ciklus vége Eljárás vége
Oszd meg és uralkodj elv A megoldandó proplémát felosztjuk kisebb részeladatokra Az egyes részfeladatokat rekurzív módon megoldjuk A részfeladatok megoldásait egyesítjük
Maximumkiválasztás
Bemenet: X – tömb, N – X elemszáma Kimenet: X elemeinek maximuma
Függvény FelezőMaximumkiválaszt(X, N) Ha N = 1 akkor return(X[1]) Különben K ← [N/2] BalMax ← FelezőMaximumkiválaszt(X[1..K],K) JobbMax ← FelezőMaximumkiválaszt(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 keresése 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
-Az ismertetett algoritmus átlagos esetében O(N)-es , de legrosszabb esetben O(N logN)-es
Merge sort Eljárás Merge-sort(X, E, U) Ha E < U akkor K← Merge-sort(X, E, K) Merge-sort(X, K + 1, U) Merge(X, E, K, U) Elágazás vége Eljárás vége
Eljárás Merge(X, E, K, U) N1 ← K – E + 1; N2 ← U – K Ciklus i ← 1-től N1-ig L[i] ← X[E + i – 1] Ciklus vége Ciklus j ← 1-től N2-ig R[j] ← X[K + j] Ciklus vége L[N1 + 1] ← +∞; R[N2 + 1] ← +∞ i ← 1; j ← 1 Ciklus k ← E-től U-ig Ha L[i] ≤ R[j] akkor X[k] ← L[i] i←i+1 Különben X[k] ← R[j] j←j+1 Elágazás vége Ciklus vége Eljárás vége
Az algoritus futási ideje: O(N * logN)-es A megvalósításthoz szükségünk van segédtömbökre, így nagyméretű tömbök esetén helyfoglalás szempontjából nem hatékony
Quicksort (rekurzív) Eljárás Quick(X, E, U) Szétválogat(X, E, U, K) Ha K – E > 1 akkor Quick(X, E, K – 1) Elágazás vége Ha U – K > 1 akkor Quick(X, K + 1, U) Elágazás vége Eljárás vége
Eljárás Szétválogat(X, E, U, K) K ← E; L ← U; A ← X[K] Ciklus amíg K < L Ciklus amíg (K < L) és (X[L] ≥ A) L←L–1 Ciklus vége Ha K < L akkor X[K] ← X[L]; K ← K + 1 Ciklus amíg (K < L) és (X[K] ≤ A) K←K+1 Ciklus vége Ha K < L akkor X[L] ← X[K]; L ← L – 1 Elágazás vége Elágazás vége Ciklus vége X[K] ← A Eljárás vége
-A Quicksort-nál alkalmazott Szétválogat metódus mindig a vizsgált résztömb első eleméhez viszonyítva válogatja két részre a résztömböt. -Emiatt pl. eleve rendezett tömb esetén az algoritmus futási ideje O(N2)-es, míg átlagos esetben csak O(N* logN)-es. Javíthatunk az algoritmuson, ha véletlenszerűen jelöljük ki, hogy melyik legyen az az elem a vizsgált résztömbből, amelyhez viszonyítva szétválogatjuk a résztömb elemeit.
