Sameiningarröðun

Úr Wikipediu, frjálsa alfræðiritinu

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

Í tölvunarfræði, er röðunarreiknirit sem hetir Sameiningarröðun(e. mergesort) og er O(n log n). Þetta er algrímur sem er stöðugur, sem þýðir að hann heldur jafnt því sem er sett inn og því sem kemur raðað út. Þetta er útgáfa af deili- og drottnunarreiknirit og þessi algrímur var fundinn upp af John von Neumann árið 1945.

[breyta] 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.

[breyta] Algrímur fyrir Sameiningarröðun

Sameiningarröðun virkar svona:

Fyrst þá skiptir maður óraðaða listanum í 2 undirlista
Skiptir síðan þessum 2 undirlistum endurkvæmnt þangað til að listarnir eru af lengd 1, þá skilum við einingalistanum til baka
Sameinum síðan þessa 2 lista í einn raðan lista.

Sameiningarröðun notar venjulega 2 hugmyndir til að keyra hraðar á keyrslutíma:

Að raða litlum lista tekur færri skref heldur en að raða stórum lista.
Færri skref eru nauðsynleg til að búa til raðan lista frá 2 röðuðum listum heldur en 2 óröðuðum listum. T.d þú þarf aðeins að fara í gegnum raðaðan lista einu sinni ef hann hefur þegar verið raðaður áður.

Dæmi: Hvernig maður getur notað Sameiningarröðun til að raða lista af heiltölum sem eru í fylki:

Mynd:Merge sort animation2.gif

Dæmi Hvernig Sameiningarröðun raðar lista af óröðuðum punktum.

Við getum haft fylki A sem er með vísir sem er frá A1 til An. Við getum notað Sameiningarröð til að raða A(A1 til Amiðja) og A(miðja+1 til An) - þar sem miðjan er heiltölu hlutinn af (A1 til An)/2. Þegar þessi 2 helmingar eru skilaðir til baka, þá hafa þeir verið raðaðir. Þá er hægt að sameina þá í einn lista til að búa til raðað fylki.

Hérna er dæmi með einföldum sauðakóða, hvernig þessi algrímur lítur út:

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

Það eru til margar útgáfur af Sameiningarröðun, hérna er dæmi um einfalda útgáfu:

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