Szybkie sortowanie - quick sort

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

Listing 1
  1. function quick_sort(data, left, right){
  2. var value = data[left];
  3. var i = left;
  4. var j = right;
  5. var temp;
  6. do{
  7. while(data[i] < value){
  8. i++;
  9. }
  10. while(data[j] > value){
  11. j --;
  12. }
  13. if(i <= j){
  14. temp = data[i];
  15. data[i] = data[j];
  16. data[j] = temp;
  17. i++;
  18. j--;
  19. }
  20. }while(i <= j);
  21. if(j > left){
  22. quick_sort(data, left, j);
  23. }
  24. if(i < right){
  25. quick_sort(data, i, right);
  26. }
  27. }

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.

Komentarze