Összefésülő rendezés

Van egy elterjedten használt rendező algoritmus, az összefésülő rendezés (merge sort). Ez egy rekurzív algoritmus. A listát két részre bontja, és a két darabot külön-külön rendezi; majd végül pedig a kapott részleteket összefésüli egy nagy, rendezett listává. A működés megértéséhez vizsgáljuk előbb meg az összefésülés algoritmusát!

Az összefésülés két rendezett listából indul ki, és azok elemeit egy harmadik listába másolja át – méghozzá úgy, hogy az új lista is rendezett lesz. Az algoritmus működésének az elve, hogy a két forrás lista elejéről mindig a kisebb elemet vesszük, és azt másoljuk a cél listába. Az összefésülés érdekessége, fontossága abban rejlik, hogy lineáris időben fut. O(n1+n2) másolással áll elő az összefésült, rendezett lista, mert minden lépésben egy elem rögtön a helyére kerül.

start következő Python kód

Lássuk mindezt Python nyelven! Három listával, és azokhoz tartozóan kettő index segítségével dolgozunk az alábbi függvényben. A t1 listához az i1 index, a t2 listához a i2 index tartozik: innen olvassuk a számokat. A cel lista tárolja az eredményt. Ahhoz nem használunk indexet, mert mindig csak az .append() függvényét hívjuk.

def osszefesul(t1, t2):
    """A két rendezett forrás, t1 és t2 elemeit összefésüli
    a visszaadott listába. Ott is rendezve lesznek."""
    cel = []
    i1 = 0
    i2 = 0
    while i1 < len(t1) or i2 < len(t2):
        if i1 < len(t1) and (i2 >= len(t2) or t1[i1] <= t2[i2]):
            cel.append(t1[i1])
            i1 += 1
        else:
            cel.append(t2[i2])
            i2 += 1
    return cel

Mindkét forrás listának az elejéről indulunk. Megnézzük, melyik elején van kisebb elem, és azt másoljuk a cél listába. Ezután a másolt elem indexe – és csak azé – megnő 1-gyel. Mindezt addig folytatjuk, amíg el nem fogytak az elemek. Tehát lényegében minden lépésben valamelyik forrás elejéről „lecsippentünk” egy elemet, mindig azt, amelyik a kisebb. (Az eleje természetesen az index által mutatott helyet jelenti, a feldolgozott elemekkel utólag már nem foglalkozunk.)

Az algoritmus legbonyolultabb része talán az, ahol kiválasztjuk, melyik lista elemét kell másolni. Itt három eset lehetséges: 1) az első lista már elfogyott, akkor a második listából kerül ki a szám, 2) a második lista fogyott el előbb, akkor az elsőből, és végül pedig 3) mindkét listában van még adat, akkor a kettő közül a kisebbik. Ezeket az eseteket írja le, kicsit megcsavarva, a ciklusban lévő elágazás feltétele. Az azt mondja, hogy akkor másolunk az első listából, ha abban van még adat i < n1, és a másikból nincs adat j >= n2 vagy az elsőben lévő szám kisebb t[i] < t[j].

Hogyan lesz ebből rendezés? Az összefésülő rendezés (merge sort) az összefésülést használja a lista rendezéséhez. Ez is egy tipikus oszd meg és uralkodj elvet használó algoritmus: a lista két különálló rendezendő részre osztja, így a két listarészlet rendezésekor egy egyszerűbb feladatot kell megoldani.

start következő

A rendezésben a két listarészletet is rendezni kell valahogyan. Itt jön képbe a rekurzió – a két részlet rendezését nem kell egy másik algoritmusra (pl. buborékrendezésre) bízni, hanem az összefésülő rendezést végző függvény meghívhatja saját magát is. A lista első felének rendezésénél ugyanez fog történni: azt a részletet is két darabra fogja osztani, annak is külön rendezi az elejét és végét, aztán összefűzi őket. Nyilvánvaló, hogy az egyre kisebb részletekkel előbb utóbb eljutunk az egy elemű listarészletekhez is, ezeket pedig már nem kell rendezni, hanem csak összefésülni. Tehát ez lesz a báziskritérium.

Az algoritmus pszeudokódja a következő:

FÜGGVÉNY rendez(lista, eleje, vége)
    HA (vége - eleje < 2)
        KÉSZ

    közepe = (eleje + vége) / 2
    rendez(lista, eleje, közepe)
    rendez(lista, közepe, vége)
    segédlista = összefésül(lista, eleje, kozepe, vege)
    másol(segédlista, eleje, vege, lista)
FÜGGVÉNY VÉGE

A függvény paraméterként egy rendezendő listát, és a rendezendő tartományt mutató indexeket kap. A tartomány balról zárt, jobbról nyílt. Pl. ha a szamok lista 0...49 indexű tartományát szeretnénk rendezni, akkor rendez(szamok, 0, 50) függvényhívást kell végeznünk. Ha az egész lista 100 elemű, akkor a másik felét rendez(szamok, 50, 100) fogja rendezni. Ezt ismerjük, ezért jó a balról zárt, jobbról nyílt intervallum: az összeérő tartományok közül az egyik végét, és másik elejét jelző szám pont ugyanaz.

Ha van mit csinálni, tehát ha a rendezendő részlet legalább két elemű, akkor a függvény meghatározza a tartomány közepét. Utána meghívja saját magát a két fél listára, és végül jöhet a végeredmény előállítása az összefésüléssel.

Az összefésülés algoritmusa két listából egy harmadikba másolta az elemeket. Emiatt az összefésülés után, a két tartomány elemei egy másik listában vannak: így azokat az összefésülés után vissza kell másolni az eredeti listába. Tehát ez az algoritmus nem nevezhető helyben rendezésnek: szüksége van egy segédlistára.

Az algoritmus lényegi része:

def rendez(lista, eleje, vege, seged):
    if vege - eleje < 2:
        return
    kozepe = (eleje + vege) // 2
    rendez(lista, eleje, kozepe, seged)
    rendez(lista, kozepe, vege, seged)
    osszefesul(tomb, eleje, kozepe, vege, seged)
    visszamasol(seged, eleje, vege, tomb)

Értelemszerűen az összefésülést és a másolást is érdemes olyan formán megírni, hogy paraméterként tartomány elejét és végét jelölő indexeket tudjanak átvenni. Ezért az összefésülést úgy módosítjuk, hogy ne maga hozza létre a cél listát, hanem egy eleve meglévő, megfelelő méretű listába másolja az adatokat, az ugyanolyan indexű helyekre, mint amilyen indexekről olvasta a forrás listából. Aztán végül az ugyanolyan indexű helyekre kell majd visszamásolni is:

def osszefesul(be, eleje, kozepe, vege, ki):
    i1 = eleje
    i2 = kozepe
    for c in range(eleje, vege):
        if i < kozepe and (j >= vege or be[i] <= be[j]):
            ki[c] = be[i]
            i += 1
        else:
            ki[c] = be[j]
            j += 1

def visszamasol(be, eleje, vege, ki):
    for c in range(eleje, vege):
        ki[c] = be[c]

Meglévő listába azért is jobb dolgozni, mert gyorsabb: nem azzal tölti a gép az idejét, hogy nyújtogatja a listát, hanem egy meglévő lista elemeit módosítjuk csak. A függvény használatához ezért létrehozunk egy segédlistát, ami kezdetben üres, és azt adjuk neki; a rendezés után a segédlista eldobható.

A függvény használata:

szamok = [ ... ]
segedlista = [None] * len(szamok)

rendez(szamok, 0, len(szamok), segedlista)
print(szamok)

A rendezés és annak segédfüggvényei elég sokat passzolgatják egymásnak az eredeti lista és a segédlista referenciáját. Ez kódolási szempontból elég kényelmetlen. A Python azonban megengedi azt, hogy függvény belsejében másik függvényt definiáljunk, és ebben az esetben a belső függvények látják a külső függvény lokális változóit is. Ennek részleteibe ez az írás nem megy bele, de a teljesség kedvéért itt szerepel az összefésülő rendezés ezt kihasználó megvalósítása:

def rendezes_osszefesulessel(lista):
    def rendez(eleje, vege):
        if vege - eleje < 2:
            return
        kozepe = (eleje + vege) // 2
        rendez(eleje, kozepe)
        rendez(kozepe, vege)
        osszefesul(eleje, kozepe, vege)
        visszamasol(eleje, vege)
        
    def osszefesul(eleje, kozepe, vege):
        i1 = eleje
        i2 = kozepe
        for c in range(eleje, vege):
            if i1 < kozepe and (i2 >= vege or lista[i1] <= lista[i2]):
                seged[c] = lista[i1]
                i1 += 1
            else:
                seged[c] = lista[i2]
                i2 += 1

    def visszamasol(eleje, vege):
        for c in range(eleje, vege):
            lista[c] = seged[c]

    seged = [None] * len(lista)
    rendez(0, len(lista))


szamok = [9, 5, 8, 7, 4, 3, 2, 6]
rendezes_osszefesulessel(szamok)
print(szamok)

A „külső függvény”, vagyis a rendezes_osszefesulessel() szerepe így az, hogy létrehozza a megfelelő méretű segédlistát, és elindítsa a rekurziót a megfelelő eleje, vege paraméterekkel. Kívülről csak ez a rendezes_osszefesulessel() függvény látszik, és ennek már csak egyetlen egy paramétere van, a rendezendő lista.