Sameiningarröðun

Sameiningarröðun sem raðar fylki af 7 heiltölum. Myndin sýnir skrefin sem maður myndi gera (frá toppi til botns).

Sameiningarröðun (e. mergesort) er tegund röðunaralgríms sem hefur tímaflækjuna O(n log n). Algrímið er er stöðugt sem þýðir að jafngild stök koma koma fyrir í sömu röð fyrir og eftir röðun. Þetta er tegund deili- og drottnunarreiknirits og var fyrst útfært af John von Neumann árið 1945.

Sameiningarröðun

Sameiningarröðun nýtir þann eiginleika hversu auðvelt það er að sameina tvo raðaða lista. Röðunin byrjar á að bera saman fyrstu tvö stökin í hvorum lista fyrir sig og afritar minna stakið (eða stærra ef raða á stærsta stakinu fyrst) í nýjan lista. Heldur síðan áfram og ber þá fyrsta stakið í listanum sem var með hærra stak í fyrsta samanburðinum við annað stakið í seinni listanum.

Röðunaraðferðin býr til þessa tvo röðuðu lista með því að skipta upprunalega listanum sem á að raða í tvennt, síðan hvorum þessarra nýju lista í tvennt aftur og svo framvegis þangað búið er að búta upprunalega listann niður í lista sem einungis geyma eitt stak hver. Að því loknu eru þessir einingalistar sameinaðir tveir og tveir í einu og mynda þá raðaðan lista með tveimur stökum. Því næst eru þeir listar sameinaðir og svo framvegis þangað til allir undirlistar hafa verið sameinaðir í heilan fullraðaðan lista.

Algrím fyrir sameiningarröðun

Hvernig sameiningarröðun raðar lista af óröðuðum punktum.

Hugmyndin bakvið sameiningarröðun byggir á eftirfarandi:

1. Hver listi sem inniheldur ekkert eða eitt stak er raðaður.
2. Hverjum lista er skipt í tvennt (má muna einu staki ef heildarfjöldi staka er oddstæð tala).
3. Sömu aðferð er svo beitt rakið á hvorn helming fyrir sig.
4. Að lokum eru listarnir, sem þá eru raðaðir, sameinaðir.

Tvennt liggur að baki hraðvirkni algrímsins:

1. Færri skref þarf til að raða stuttum listum.
2. Færri skref þarf til þess að sameina tvo raðaða lista í raðaðan lista en þarf til þess að sameina tvo óraðaða lista í raðaðan lista.

Eftirfarandi er dæmi um sameiningarröðun á blendingsmáli:

function mergesort(m)
    var list left, right, result
    if length(m) ≤ 1
        return m
    else
        var middle = length(m) / 2
        for each x in m up to middle
            add x to left
        for each x in m after middle
            add x to right
        left = mergesort(left)
        right = mergesort(right)
        result = merge(left, right)
        return result

Útfæra má sameiningarstefið (e. merge) með ýmsum hætti, hér er einföld útfærsla á blendingsmáli:

function merge(left,right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
    if length(left) > 0 
        append rest(left) to result
    if length(right) > 0 
        append rest(right) to result
    return result

Heimildir

• Fyrirmynd greinarinnar var „Merge sort“ á ensku útgáfu Wikipedia. Sótt 21. mars 2008.