Az összefésülő rendezés áttekintése

Mivel az oszd meg és uralkodj technikát alkalmazzuk, el kell döntenünk, mik legyenek a részfeladatok. A teljes feladat egy egész tömb rendezése. Mondjuk azt, hogy a részfeladat egy résztömb rendezése lesz. Úgy fogjuk meghatározni a részfeladatot, hogy abban egy résztömböt egy $p$‍ indextől egy $r$‍ indexig fogjuk rendezni. A könnyebbség kedvéért vezessünk be egy jelölésmódot egy adott résztömb megjelölésére, jelölje array[p..r] az array tömb fent kijelölt résztömbjét. Fontos tudni, hogy ez a „kétpontos” jelölés nem egy érvényes JavaScript jelölésrendszer: csak az algoritmus leírásának megkönnyítése kedvéért alkalmazzuk, nem a programkód egy megvalósítását céloztuk meg. Jelölésrendszerünk felhasználásával azt mondhatjuk, hogy egy $n$‍ elemű tömb rendezését megfogalmazhatjuk úgy, hogy rendezni szeretnénk array[0..n-1]-et.

Így használja az összefésülő rendezés az oszd-meg-és-uralkodj elvet:

Kell egy alapeset. Az alapeset a kettőnél kevesebb elemet tartalmazó résztömb lesz, azaz amikor $p\ge r$‍, mivel az üres vagy a csak egy elemet tartalmazó résztömb már rendezett. Tehát megosztani-uralkodni-összefésülni csak akkor kell, amikor $p<r$‍.

Nézzünk egy példát. Kezdjük a [14, 7, 3, 12, 9, 11, 6, 2]-t tartalmazó array tömbbel. Az első résztömb a teljes array[0..7] tömb lesz ($p=0$‍ és $r=7$‍). Ennek a résztömbnek legalább két eleme van, úgyhogy ez nem alapeset.

Hogyan vált az array[0..3] résztömb rendezetté? Ugyanúgy. Kettő, vagy több elemet tartalmaz, azaz nem alapeset. $p=0$‍ és $r=3$‍ alapján kiszámoljuk $q=1$‍-et, rekurzívan rendezzük array[0..1]-t ([14, 7]) és array[2..3]-t ([3, 12]), amiből megkapjuk array[0..3]-t [7, 14, 3, 12] tartalommal. Összefésülve az első és második részt [3, 7, 12, 14]-et kapunk.

Mitől lett az array[0..1] résztömb rendezett? $p=0$‍ és $r=1$‍ alapján kiszámoljuk $q=0$‍-t, rekurzívan rendezzük array[0..0]-t ([14]) és array[1..1]-t ([7]), amiből megkapjuk array[0..1]-t, változatlanul [14, 7] tartalommal. Összefésüljük az első és a második részt, így megkapjuk a [7, 14]-et.

Az array[0..0] és array[1..1] résztömbök alapesetek, mert mindkettőben kettőnél kevesebb elem található. Itt látható a teljes összefésülő rendezés folyamata:

Az összefésülő rendezés legtöbb lépése egyszerű. Az alapeset könnyen ellenőrizhető. Az oszd meg lépésben a $q$‍ középpont megtalálása sem bonyolult. Az uralkodj lépésben két rekurzív hívásra van szükség. Az összefésülés lépésben történik az igazi munka, ahol a két rendezett résztömböt egyesíted.

A most következő feladatban az összefésülő algoritmus keretének implementálása lesz a cél, hogy biztosan megértsd, hogyan kell rekurzívan megosztani és uralkodni. Miután végeztél, részletesebben megvizsgáljuk, hogyan kell két rendezett résztömböt hatékonyan összefésülni, amit majd egy későbbi feladat során fogsz megvalósítani.

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.