Szybkie sortowanie - quick sort
Stronę tą wyświetlono już: 5057 razy
Sortowanie szybkie (quick sort) jest algorytmem rekurencyjnym, który dzieli dany zbiór na mniejsze części względem wybranego elementu sortowanej tablicy do momentu uzyskania tablicy o rozmiarze równym 1. W trakcie podziału elementy tablicy sortowanej mniejsze od wybranej wartości są zamieniane miejscami z większymi. W ten sposób dane częściowo są posegregowane. Na najniższych gałęziach uzyskuje się pełny stopień posortowania, który gwarantuje posortowanie całego zbioru. Ze względów wydajnościowych algorytm ten jest rozszerzany w taki sposób, że dla zbiorów o liczebności mniejszej niż 25 stosuje się inne (bardziej wydajne) algorytmy sortowania (np. sortowanie przez wstawianie - insertion sort).
Przykład implementacji algorytmu z podziałem zbiorów na podzbiory ≤ 2 napisanej w JavaScript:
Złożoność obliczeniowa tego algorytmu jest szacowana na n log n w sprzyjających zazwyczaj warunkach, zaś n2 w warunkach niesprzyjających.
Paradoksalnie najbardziej niekorzystną sytuacją jest, gdy zbiór sortowanych liczb składa się np. z takich samych liczb gdyż dla takiego przypadku algorytm za każdym razem dokonuje niepotrzebnej zamiany miejscami i to w każdym podziale.
Tytuł:
Algorytmy. Ilustrowany przewodnik
Autor:
Aditya Bhargava
Tytuł:
Algorytmy. Struktury danych i złożoność obliczeniowa
Autor:
Feliks Kurp
Tytuł:
Algorytmy w Pythonie. Techniki programowania dla praktyków
Autor:
Piotr Wróblewski
Tytuł:
Matematyka dyskretna dla praktyków. Algorytmy i uczenie maszynowe w Pythonie
Autor:
Ryan T. White, Archana Tikayat Ray
Tytuł:
Algorytmy kryptograficzne w Pythonie. Wprowadzenie
Autor:
Shannon W. Bray
Tytuł:
Algorytmy sztucznej inteligencji. Ilustrowany przewodnik
Autor:
Rishal Hurbans
Tytuł:
Algorytmy bez tajemnic
Autor:
Thomas H. Cormen
Tytuł:
Algorytmy dla bystrzaków
Autor:
John Paul Mueller, Luca Massaron
Tytuł:
Algorytmy Data Science. Siedmiodniowy przewodnik. Wydanie II
Autor:
David Natingga
Tytuł:
Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji
Autor:
Giuseppe Bonaccorso