Programozás‎ > ‎Rendezések‎ > ‎

Összefésülő rendezés

Gondolat

A tömböt két részre vágjuk (lehetőleg fele-fele arányban), a részeket külön-külön rendezzük (rekurzió!), majd a rendezett részeket összefésüljük.

Összefésülés

A rendezett tömbök első elemire állunk, és minden lépésben a két aktuális elem közül a kisebbet tesszük az eredmény tömbbe, majd annak mutatóját növeljük. Ha valamelyik részt végigolvastuk már, akkor egyszerűen a másik részből másolgatjuk az elemeket.

Algoritmus

rendez(E, U):

    Ha E < U akkor
        K := (E+U) / 2
        rendez(E,K)
        rendez(K+1,U)
        összefésül(E,K,U)
    Elágazás vége


összefésül(E,K,U):

    tmp[E..U] : = a[E..U] // tömb másolása átmeneti tárolóhelyre
    i := E; j := K+1
    Ciklus id := E-től U-ig
        Ha i > K akkor
            a[id] := tmp[j]
            j := j+1
        különben Ha j > U akkor
            a[id] := tmp[i]
            i := i+1
        különben Ha tmp[i] < tmp[j] akkor
            a[id] := tmp[i]
            i := i+1
        különben
            a[id] := tmp[j]
            j := j+1
        Elágazás vége
    Ciklus vége