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 Θ(n2) \Theta(n^2) . 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 Θ(nlgn) \Theta(n \lg n) we wszystkich przypadkach, a szybkie sortowanie w czasie Θ(nlgn) \Theta(n \lg n) w najlepszym i średnim przypadku, a czas jego wykonania w najgorszym wypadku wynosi Θ(n2) \Theta(n^2) . Poniżej zamieszczona jest tabela zawierająca te cztery rodzaje sortowania i czasy ich wykonania:
AlgorytmCzas wykonania w najgorszym przypadkuCzas wykonania w najlepszym przypadkuŚredni czas wykonania
Sortowanie przez wybieranieΘ(n2) \Theta(n^2) Θ(n2) \Theta(n^2) Θ(n2) \Theta(n^2)
Sortowanie przez wstawianieΘ(n2) \Theta(n^2) Θ(n) \Theta(n) Θ(n2) \Theta(n^2)
Sortowanie przez scalanieΘ(nlgn) \Theta(n \lg n) Θ(nlgn) \Theta(n \lg n) Θ(nlgn) \Theta(n \lg n)
QuicksortΘ(n2) \Theta(n^2) Θ(nlgn) \Theta(n \lg n) Θ(nlgn) \Theta(n \lg n)

Dziel-i-rządź

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:
  1. Podziel problem na pewną liczbę podproblemów, które są mniejszymi przypadkami tego samego problemu.
  2. Rządź podproblemami, rozwiązując je rekurencyjnie. Jeśli są wystarczająco małe, rozwiąż podproblemy jako przypadki bazowe.
  3. Połącz rozwiązania poszczególnych podproblemów w jedno rozwiązanie pierwotnego problemu.
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.
Ładowanie