Autor podstrony: Krzysztof Zajączkowski

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

function quick_sort(data, left, right){ var value = data[left]; var i = left; var j = right; var temp; do{ while(data[i] < value){ i++; } while(data[j] > value){ j --; } if(i <= j){ temp = data[i]; data[i] = data[j]; data[j] = temp; i++; j--; } }while(i <= j); if(j > left){ quick_sort(data, left, j); } if(i < right){ quick_sort(data, i, right); } }

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.

Tematy powiązane