Szybkie sortowanie - quick sort

Autor podstrony: Krzysztof Zajączkowski

Stronę tą wyświetlono już: 5054 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).

Rys. 1

Animacja pokazująca działanie algorytmu szybkiego sortowania (quick sort):

niebieski - elementy tablicy podlegające procesowi podziału;
czerwony - elementy tablicy posortowane częściowo lub całkowicie;
pomarańczowy - zamieniane/zamienione stronami wartości;
ciemno zielony - element tablicy, zawierający wartość porównywaną tablicy;
jasno zielony - pozostałe elementy tablicy;

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ś n² 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.