Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 1
Lekcja 8: Sortowanie przez scalanieAlgorytmy 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, 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, left parenthesis, n, \lg, n, right parenthesis we wszystkich przypadkach, a szybkie sortowanie w czasie \Theta, left parenthesis, n, \lg, n, right parenthesis w najlepszym i średnim przypadku, a czas jego wykonania w najgorszym wypadku wynosi \Theta, left parenthesis, n, squared, right parenthesis. Poniżej zamieszczona jest tabela zawierająca te cztery rodzaje sortowania i czasy ich wykonania:
Algorytm | Czas wykonania w najgorszym przypadku | Czas wykonania w najlepszym przypadku | Średni czas wykonania |
---|---|---|---|
Sortowanie przez wybieranie | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, squared, right parenthesis |
Sortowanie przez wstawianie | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, right parenthesis | \Theta, left parenthesis, n, squared, right parenthesis |
Sortowanie przez scalanie | \Theta, left parenthesis, n, \lg, n, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis |
Quicksort | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis |
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:
- Podziel problem na pewną liczbę podproblemów, które są mniejszymi przypadkami tego samego problemu.
- Rządź podproblemami, rozwiązując je rekurencyjnie. Jeśli są wystarczająco małe, rozwiąż podproblemy jako przypadki bazowe.
- 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.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji