Sameiningarröðun

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 sem raðar fylki af 7 heiltölum. Myndin sýnir skrefin sem maður myndi gera (frá toppi til botns).

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.