Oszd meg és uralkodj algoritmusok

Az eddig látott két rendező algoritmus, a minimumkiválasztásos rendezés és a beszúró rendezés legrosszabb futási ideje $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. Nagyméretű input tömb esetén ezeknek az algoritmusoknak hosszú lehet a futási idejük. Ebben és a következő fejezetben két másik rendezési algoritmust veszünk górcső alá, az összefésülő rendezést és a gyorsrendezést, amiknek jobb a futási idejük. Az összefésülő rendezés minden esetben $\Theta(n \lg n)$\Theta, left parenthesis, n, \lg, n, right parenthesis idő alatt fut le, a gyorsrendezés futási ideje a legjobb esetben, valamint átlagosan $\Theta(n \lg n)$\Theta, left parenthesis, n, \lg, n, right parenthesis, viszont a legrosszabb esetben $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. Az alábbi táblázatban összefoglaltuk e négy rendezési algoritmus futási idejét a legjobb, az átlagos és a legrosszabb esetben:

Mind az összefésülő rendezés, mind a gyorsrendezés ugyanazt a rekurzión alapuló paradigmát használja fel az algoritmus során. Ez a paradigma az oszd meg és uralkodj elv, ami azon alapul, hogy a megoldandó feladatot az eredetihez hasonló részfeladatokra bontja, megoldja azokat, majd a megoldott részfeladatokat összefésüli. Mivel az oszd-meg-és-uralkodj folyamat során a részfeladatokat rekurzívan oldja meg, az egyes részfeladatoknak az eredetinél mindig kisebbnek kell lenniük, és léteznie kell a részfeladatok alapesetének is. Az oszd-meg-és-uralkodj algoritmus három összetevőből áll:

Az oszd meg és uralkodj algoritmusok egyes lépéseit az alábbi tevékenységek sorozataként jegyezd meg: oszd fel részproblémákra, urald a részproblémákat, fésüld össze az eredményeket. Egy adott lépést a következőképpen szemléltethetünk, feltéve, hogy a felosztás során mindig két részfeladatot képezünk (vannak olyan oszd meg és uralkodj algoritmusok, melyek kettőnél több részfeladatot képeznek):

Ha egy vagy több rekurzív lépést kibontunk, akkor ezt kapjuk:

Mivel az oszd meg és uralkodj legalább két részfeladatot képez, ezért az több rekurzív hívást eredményez.

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.