Z Wikipedii

Sortowanie szybkie

Sortowanie szybkie (ang. quicksort) – jeden z popularnych algorytmów sortowania działających na zasadzie "dziel i zwyciężaj".

Sortowanie QuickSort zostało wynalezione w 1960 przez C.A.R. Hoare'a^[1].

[edytuj] Zasada

Algorytm działa rekursywnie - wybieramy pewien element tablicy, tzw. element osiowy, po czym na początek tablicy przenosimy wszystkie elementy mniejsze od niego, na koniec wszystkie większe, a w powstałe między tymi obszarami puste miejsce trafia wybrany element. Potem sortujemy osobno początkową i końcową część tablicy. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa podtablica nie wymaga oczywiście sortowania.

Jeśli przez l oznaczymy indeks pierwszego, a przez r – ostatniego elementu sortowanego fragmentu tablicy, zaś przez i – indeks elementu, na którym tablica została podzielona, to procedurę sortowania można (w dużym uproszczeniu) przedstawić następującym, pascalo-podobnym zapisem:

  PROCEDURE Quicksort(l, r)
  BEGIN
    IF l < r THEN                { jeśli fragment dłuższy niż 1 element }
    BEGIN
      i = PodzielTablice(l, r);  { podziel i zapamiętaj punkt podziału }
      Quicksort(l, i-1);         { posortuj lewą część }
      Quicksort(i, r);           { posortuj prawą część }
    END
  END

Algorytm sortowania szybkiego jest bardzo wydajny: jego Å›rednia zÅ‚ożoność obliczeniowa jest rzÄ™du O(n·log n) (zob. hasÅ‚o Notacja dużego O). Jego szybkość i prostota implementacji powodujÄ…, że jest powszechnie używany; jego implementacje znajdujÄ… siÄ™ również w standardowych bibliotekach jÄ™zyków programowania - na przykÅ‚ad w bibliotece standardowej jÄ™zyka C, w implementacji klasy TList w Delphi, jako procedura standardowa w PHP itp.

[edytuj] Złożoność

Algorytm ten dość dobrze działa w praktyce, ale ma bardzo złą pesymistyczną złożoność.

[edytuj] Przypadek optymistyczny

W przypadku optymistycznym, jeśli mamy szczęście za każdym razem wybrać medianę z sortowanego fragmentu tablicy, to liczba porównań niezbędnych do uporządkowania n-elementowej tablicy opisana jest rekurencyjnym wzorem

Dla dużych n:

co daje w rozwiązaniu liczbę porównań (a więc wskaźnik złożoności czasowej):

Równocześnie otrzymuje się minimalne zagnieżdżenie rekursji (czyli głębokość stosu, a co za tym idzie, złożoność pamięciową):

[edytuj] Przypadek przeciętny

W przypadku przeciętnym, to jest dla równomiernego rozkładu prawdopodobieństwa wyboru elementu z tablicy:

złożoność jest zaledwie o 39% wyższa, niż w przypadku optymistycznym.

[edytuj] Przypadek pesymistyczny

W przypadku pesymistycznym, jeśli zawsze wybierzemy element najmniejszy (albo największy) w sortowanym fragmencie tablicy, to:

skąd wynika kwadratowa złożoność czasowa:

W tym przypadku otrzymuje się też olbrzymią, liniową złożoność pamięciową:

[edytuj] Usprawnienia algorytmu

[edytuj] Wybór elementu

Najprostsza, "naiwna" metoda podziaÅ‚u – wybieranie zawsze skrajnego elementu tablicy – dla danych już uporzÄ…dkowanych daje katastrofalnÄ… zÅ‚ożoność O(n²). Trywialne na pozór zadanie posortowania posortowanej tablicy okazuje siÄ™ dla tak zapisanego algorytmu zadaniem skrajnie trudnym. Aby uchronić siÄ™ przed takim przypadkiem stosuje siÄ™ najczęściej randomizacjÄ™ wyboru albo wybór "Å›rodkowy z trzech". Pierwszy sposób opiera siÄ™ na losowaniu elementu osiowego, co sprowadza prawdopodobieÅ„stwo zajÅ›cia najgorszego przypadku do wartoÅ›ci zaniedbywalnie maÅ‚ych. Drugi sposób polega na wstÄ™pnym wyborze trzech elementów z rozpatrywanego fragmentu tablicy, i użyciu jako elementu osiowego tego z trzech, którego wartość leży pomiÄ™dzy wartoÅ›ciami pozostaÅ‚ych dwu. Można również uzupeÅ‚nić algorytm o poszukiwanie przybliżonej mediany (patrz poniżej: #Gwarancja zÅ‚ożonoÅ›ci).

[edytuj] Ograniczenie rekursji

Wysoka wydajność alogrytmu sortowania szybkiego predestynuje go do przetwarzania dużych tablic. Takie zastosowanie wymaga jednak zwrócenia szczególnej uwagi na głębokość rekursji. Głębokość rekursji wiąże się bowiem z wykorzystaniem stosu maszynowego.

W najgorszym przypadku, jeśli algorytm będzie dzielił tablicę zawsze na część jednoelementową i resztę, to rekursja osiągnie głębokość n-1. Aby temu zapobiec, należy sprawdzać, która część jest krótsza – i tę porządkować najpierw. Z dłuższą zaś nie wchodzić w rekursję, lecz ponownie dzielić na tym samym poziomie wywołania:

  PROCEDURE Quicksort( l, r )
  BEGIN
    WHILE l < r DO                 { dopóki fragment dłuższy niż 1 element }
    BEGIN
      i := PodzielTablice( l, r );
      IF (i-l) ≤ (r-i) THEN        { sprawdź, czy lewa część krótsza }
        BEGIN                      { TAK? }
          Quicksort( l, i-1 );     { posortuj lewą, krótszą część }
          l := i+1                 { i kontynuuj dzielenie dłuższej }
        END
      ELSE
        BEGIN                      { NIE }
          Quicksort( i, r );       { posortuj prawą, krótszą część }
          r := i-1                 { i kontynuuj dzielenie dłuższej }
        END
    END
  END

Przy takiej organizacji pracy na stosie zawsze pozostajÄ… zapamiÄ™tane (w zmiennych i, r albo l, i) indeksy ograniczajÄ…ce dÅ‚uższÄ…, jeszcze nie posortowanÄ… część tablicy, a wywoÅ‚anie rekurencyjne zajmuje siÄ™ częściÄ… krótszÄ…. To znaczy, że na każdym poziomie wywoÅ‚aÅ„ algorytm obsÅ‚uguje fragment bÄ™dÄ…cy co najwyżej poÅ‚owÄ… fragmentu z poprzedniego poziomu. StÄ…d wynika, że poziomów wywoÅ‚aÅ„ nie bÄ™dzie wiÄ™cej, niż log₂n, gdzie n oznacza dÅ‚ugość caÅ‚ej tablicy. Zatem usprawnienie to zmienia asymptotyczne wykorzystanie pamiÄ™ci tego algorytmu z O(n) do O(log₂n).

[edytuj] Quicksort w miejscu

Istnieje modyfikacja czyniąca algorytm quicksort działającym w miejscu. W oryginalnym sortowaniu szybkim używa się rekursji lub stosu (de facto oba sposoby niewiele się różnią – rekursja w uproszczeniu jest niejawnym stosem) do zapamiętywania miejsc podziału. Więc chociaż algorytm w obu wersjach nie korzysta z dodatkowych tablic o rozmiarze zależnym od rozmiaru danych wejściowych, to nie można nazywać go działającym w miejscu, gdyż wysokość, a więc i wymagania pamięciowe wywołań rekusji/stosu są ściśle zależne od rozmiaru danych początkowych.

Załóżmy, że dla sortowanej tablicy A funkcja PodzielTablice(l,p) zwróciła wartość s. W oryginalnym algorytmie quicksort powinno zostać wykonane wywołania Quicksort(l,s-1) i Quicksort(s+1,p). Zamiast tego "zajmujemy się" tylko Quicksort(l,s-1), a pozycje s+1 i p zapamiętujemy w następujący sposób:

• s+1: jest jednoznacznie wyznaczona przez koniec ciÄ…gu (l,s-1) → (s+1) = (s-1) + 2
• p: znajdujemy maksimum ciÄ…gu (s+1,p) i zamieniamy tÄ™ pozycjÄ™ z pozycjÄ… s. Aby odtworzyć pozycjÄ™ p, wystarczy przeszukiwać ciÄ…g w prawo do znalezienia elementu wiÄ™kszego od wartoÅ›ci stojÄ…cej na pozycji s. Wtedy indeks elementu o najmniejszej wartoÅ›ci wiÄ™kszej od A[s] to p+1.

Metoda ta sprowadza koszt pamięciowy algorytmu do wartości stałej, O(1), wymaga jednak dodatkowego nakładu czasu na wyszukiwanie maksymalnych elementów kolejno sortowanych fragmentów tablicy. Ujmuje więc algorytmowi jego główną zaletę, wpisaną nawet w jego nazwę – szybkość działania.

[edytuj] Drobne fragmenty

U podstaw kolejnego usprawnienia leży spostrzeżenie, że około połowa wszystkich rekurencyjnych wywołań procedury dotyczy jednoelementowych fragmentów tablicy – a więc fragmentów z definicji posortowanych. Co więcej, po wliczeniu dodatkowej pracy potrzebnej na wybór elementu dzielącego i zorganizowanie pętli dzielącej tablicę okazuje się, że sortowanie tablic nawet kilkuelementowych algorytmem quicksort jest bardziej pracochłonne, niż jakimś algorytmem prostym, na przykład przez wstawianie.

Warto więc zaniechać dalszych podziałów, gdy uzyskane fragmenty staną się dostatecznie krótkie – rzędu kilku lub kilkunastu elementów. Otrzymuje się w wyniku tablicę "prawie posortowaną", w której większość elementów może nie znajduje się na właściwych miejscach, ale są blisko właściwych miejsc. Taką tablicę ostatecznie sortuje się algorytmem wstawiania, który bardzo efektywnie radzi sobie z tego rodzaju danymi. Jak pokazuje praktyka, wybór granicznej długości fragmentu nie wymaga szczególnych rygorów – algorytm działa niemal równie dobrze dla wartości od 5 do 25. W większości zastosowań pozwala to osiągnąć oszczędność łącznego czasu wykonania rzędu 20%.

[edytuj] Gwarancja złożoności

Pomimo wszelkich usprawnieÅ„, pozostaje jednak, zazwyczaj znikome, prawdopodobieÅ„stwo zajÅ›cia przypadku pesymistycznego, w którym zÅ‚ożoność czasowa wynosi O(n²). JeÅ›li chcemy mieć pewność wykonania sortowania w czasie nie dÅ‚uższym niż O(nlog₂n), należy uzupeÅ‚nić algorytm o poszukiwanie przybliżonej mediany, czyli elementu dzielÄ…cego posortowanÄ… tablicÄ™ na tyle dobrze, że pesymistyczne oszacowanie zÅ‚ożonoÅ›ci zrówna siÄ™ z optymistycznym.

Jeżeli prawdopodobieństwo wystąpienia przypadku pesymistycznego w praktyce jest duże, to można skorzystać ze specjalnych algorytmów znajdowania dobrej mediany. Niestety algorytmy te mają dość dużą złożoność, dlatego w takiej sytuacji należy też rozważyć skorzystanie z innych algorytmów sortowania, takich jak np. sortowanie stogowe, sortowanie pozycyjne, czy sortowanie przez scalanie.

W większości praktycznych zastosowań algorytm sortowania szybkiego jest bezkonkurencyjny. W praktyce pozostaje on zdecydowanie najczęściej używanym algorytmem sortowania. Opracowano też wiele modyfikacji i usprawnień tego algorytmu, poprawiając niektóre właściwości, lub dostosowując go do konkretnych wymagań.

[edytuj] Przykładowe implementacje

[edytuj] Pascal

Kod szybkiego sortowania tablicy w Pascalu (z randomizowanym wyborem elementu dzielącego, lecz bez pozostałych usprawnień).

   PROCEDURE Quicksort (VAR A : tab; l,r: INTEGER);
   VAR 
       pivot,b,i,j :  INTEGER;
   BEGIN 
       IF l < r THEN
       BEGIN
           pivot := A[random(r-l) + l+1];  { losowanie elementu dzielÄ…cego }
           i := l-1;
           j := r+1;
           REPEAT
               REPEAT i := i+1 UNTIL pivot <= A[i];
               REPEAT j := j-1 UNTIL pivot >= A[j];
               b:=A[i]; A[i]:=A[j]; A[j]:=b
           UNTIL i >= j;
           A[j]:=A[i]; A[i]:=b;
           Quicksort(A,l,i-1);
           Quicksort(A,i,r)
       END
   END;

Wywoływanie dla tablicy o długości n: quicksort(tablica,1,n);.

[edytuj] SML

Kod szybkiego sortowania w SML

infix 5 <<;
infix 5 >>;

fun x << (y::ys) = if (y < x) then y::(x << ys) else x << ys
  | x << nil = nil;

fun x >> (y::ys) = if (y >= x) then y::(x >> ys) else x >> ys
  | x >> nil = nil;

fun quicksort nil = nil
  | quicksort [x] = [x]
  | quicksort (x::xs) = quicksort(x << xs) @ (x::quicksort(x >> xs))

(* np. sortuj int list *)
quicksort [108,14,13,15];

(* albo krócej *)
fun qs [] = [] 
  | qs (x::xs) = (qs (filter (fn p => p < x) xs)) @ (x::(qs (filter (fn p => p>= x) xs)))

[edytuj] ANSI C

Funkcja w jÄ™zyku ANSI C (dla tablicy o elementach typu float i dÅ‚ugoÅ›ci typu int) :

typedef float TYP;
 
void QuickSort(TYP *T, int Lo, int Hi)
{
   int i,j;
   TYP x;
   x = T[(Lo+Hi)/2];
   i = Lo;
   j = Hi;
   do
   {
      while (T[i] < x) ++i;
      while (T[j] > x) --j;
      if (i<=j)
      {
         TYP tmp = T[i];
         T[i] = T[j];
         T[j] = tmp;
         ++i; --j;
      }
   } while(i < j);
   if (Lo < j) QuickSort(T, Lo, j);
   if (Hi > i) QuickSort(T, i, Hi);
}

[edytuj] C++

Implementacja w języku C++ przy założeniu, że elementem osiowym jest skrajny element tablicy.

#include <algorithm> // std::swap (funkcja zamieniająca dwie wartości między sobą)
 
void qsort(int tab[],int lewy,int prawy)
{
   if(lewy<prawy)
   {
      int m=lewy;
      for(int i=lewy+1;i<=prawy;i++)
         if(tab[i]<tab[lewy])
            std::swap(tab[++m],tab[i]);
      std::swap(tab[lewy],tab[m]);
      qsort(tab,lewy,m-1);
      qsort(tab,m+1,prawy);
   }
}

Przypisy

[edytuj] Zobacz też

• sortowanie