Algorytmy dziel i zwyciężaj

Dwa algorytmy sortowania, które poznaliśmy do tej pory, sortowanie przez wybieranie oraz sortowanie przez wstawianie, mają w najgorszym przypadku czas wykonania rzędu $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. Jeśli rozmiar tablicy wejściowej byłby bardzo duży, sortowanie tymi metodami mogłoby zająć bardzo dużo czasu. W tym samouczku i w następnym, poznamy dwa inne algorytmy sortowania: sortowanie przez scalanie (merge) i szybkie sortowanie (quicksort), których czas wykonania jest krótszy. Sortowanie przez scalanie wykonuje się w czasie $\Theta(n \lg n)$\Theta, left parenthesis, n, \lg, n, right parenthesis we wszystkich przypadkach, a szybkie sortowanie w czasie $\Theta(n \lg n)$\Theta, left parenthesis, n, \lg, n, right parenthesis w najlepszym i średnim przypadku, a czas jego wykonania w najgorszym wypadku wynosi $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. Poniżej zamieszczona jest tabela zawierająca te cztery rodzaje sortowania i czasy ich wykonania:

Zarówno sortowanie przez scalanie, jak i szybkie sortowanie wykorzystują wspólny paradygmat algorytmiczny, oparty na rekurencji. Ten paradygmat, dziel-i-rządź, dzieli problem na podproblemy, które są podobne do pierwotnego problemu, rekurencyjnie rozwiązuje podproblemy, a następnie łączy ze sobą rozwiązania tych podproblemów, aby rozwiązać pierwotny problem. Ze względu na to, że dziel-i-rządź rozwiązuje podproblemy rekurencyjnie, każdy podproblem musi być mniejszy niż problem pierwotny i musi istnieć przypadek bazowy dla podproblemów. Pomyślmy o paradygmacie dziel-i-rządź jako o algorytmie złożonym z trzech części:

Z łatwością możemy zapamiętać kroki algorytmu dziel-i-rządź jako podziel, rządź, połącz. Poniższy obrazek pokazuje nam jeden krok algorytmu, przy założeniu, że operacja dzielenia problemu tworzy dwa podproblemy (choć niektóre algorytmy dziel-i-rządź tworzą więcej niż dwa podproblemy):

Jeśli rozszerzymy to na dwa lub więcej kroki rekurencyjne, wygląda to w następujący sposób:

Ze względu na fakt, iż algorytm dziel-i-rządź tworzy przynajmniej dwa podproblemy, jest on algorytmem wykonującym wielokrotne wywołania rekurencyjne.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.