Algorytm sortowania szybkiego opiera się na strategii "dziel i zwyciężaj" (ang. divide and conquer), którą możemy krótko scharakteryzować w trzech punktach:

1. DZIEL - problem główny zostaje podzielony na podproblemy
2. ZWYCIĘŻAJ - znajdujemy rozwiązanie podproblemów
3. POŁĄCZ - rozwiązania podproblemów zostają połączone w rozwiązanie problemu głównego

Idea sortowania szybkiego jest następująca:

prof. Tony Hoare

Sortowanie szybkie zostało wynalezione przez angielskiego informatyka, profesora Tony'ego Hoare'a w latach 60-tych ubiegłego wieku. W przypadku typowym algorytm ten jest najszybszym algorytmem sortującym z klasy złożoności obliczeniowej O(n log n) - stąd pochodzi jego popularność w zastosowaniach. Musimy jednak pamiętać, iż w pewnych sytuacjach (zależnych od sposobu wyboru piwotu oraz niekorzystnego ułożenia danych wejściowych) klasa złożoności obliczeniowej tego algorytmu może się degradować do O(n²), co więcej, poziom wywołań rekurencyjnych może spowodować przepełnienie stosu i zablokowanie komputera. Z tych powodów algorytmu sortowania szybkiego nie można stosować bezmyślnie w każdej sytuacji tylko dlatego, iż jest uważany za jeden z najszybszych algorytmów sortujących - zawsze należy przeprowadzić analizę możliwych danych wejściowych właśnie pod kątem przypadku niekorzystnego - czasem lepszym rozwiązaniem może być zastosowanie wcześniej opisanego algorytmu sortowania przez kopcowanie, który nigdy nie degraduje się do klasy O(n²).

Tworzenie partycji

Do utworzenia partycji musimy ze zbioru wybrać jeden z elementów, który nazwiemy piwotem. W lewej partycji znajdą się wszystkie elementy niewiększe od piwotu, a w prawej partycji umieścimy wszystkie elementy niemniejsze od piwotu. Położenie elementów równych nie wpływa na proces sortowania, zatem mogą one występować w obu partycjach. Również porządek elementów w każdej z partycji nie jest ustalony.

Jako piwot można wybierać element pierwszy, środkowy, ostatni, medianę lub losowy. Dla naszych potrzeb wybierzemy element środkowy:

Dzielenie na partycje polega na umieszczeniu dwóch wskaźników na początku zbioru - i oraz j. Wskaźnik i przebiega przez zbiór poszukując wartości mniejszych od piwotu. Po znalezieniu takiej wartości jest ona wymieniana z elementem na pozycji j. Po tej operacji wskaźnik j jest przesuwany na następną pozycję. Wskaźnik j zapamiętuje pozycję, na którą trafi następny element oraz na końcu wskazuje miejsce, gdzie znajdzie się piwot. W trakcie podziału piwot jest bezpiecznie przechowywany na ostatniej pozycji w zbiorze.

Przykład:

Dla przykładu podzielimy na partycje zbiór: { 7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3 }

 7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3 

 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 

 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
 i 
 j 

 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
   i 
 j 

 2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
   i 
   j 

 2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
     i 
   j 

 2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
     i 
     j 

 2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
         i 
     j 

 2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 
         i 
       j 

 2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 
           i 
       j 

 2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 
           i 
         j 

 2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 
             i 
         j 

 2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 
             i 
           j 

 2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 
                 i 
           j 

 2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 
                 i 
             j 

 2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 
                     i 
             j 

 2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 
                     i 
               j 

 2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 
                         i 
               j 

 2 4 3 1 4 3 3 2 7 8 7 9 6 6 7 6 5 
                         i 
                 j 

 2 4 3 1 4 3 3 2 5 8 7 9 6 6 7 6 7 
                 ^             i   
Lewa partycja    j   Prawa partycja

Po zakończeniu podziału na partycje wskaźnik j wyznacza pozycję piwotu. Lewa partycja zawiera elementy mniejsze od piwotu i rozciąga się od początku zbioru do pozycji j - 1. Prawa partycja zawiera elementy większe lub równe piwotowi i rozciąga się od pozycji j + 1 do końca zbioru. Operacja podziału na partycje ma liniową klasę złożoności obliczeniowej - O(n).

Specyfikacja problemu

Sortuj_szybko(lewy, prawy)

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

K01:
K02:	piwot ← d[i];   d[i] ← d[prawy];   j ← lewy
K03:	Dla i = lewy, lewy + 1, ..., prawy - 1:     wykonuj kroki K04...K05
K04:	Jeśli d[i] ≥ piwot,     to wykonaj kolejny obieg pętli K03
K05:	d[i] ↔ d[j];    j ← j + 1
K06:	d[prawy] ← d[j];   d[j] ← piwot
K07:	Jeśli lewy < j - 1, to Sortuj_szybko(lewy, j - 1)
K08:	Jeśli j + 1 < prawy, to Sortuj_szybko(j + 1, prawy)
K09:	Zakończ

Algorytm sortowania szybkiego wywołujemy podając za lewy indeks pierwszego elementu zbioru, a za prawy indeks elementu ostatniego (czyli Sortuj_szybko(1,n)). Zakres indeksów jest dowolny - dzięki temu ten sam algorytm może również sortować fragment zbioru, co wykorzystujemy przy sortowaniu wyliczonych partycji.

Schemat blokowy

Na element podziałowy wybieramy element leżący w środku dzielonej partycji. Wyliczamy jego pozycję i zapamiętujemy ją tymczasowo w zmiennej i. Robimy to po to, aby dwukrotnie nie wykonywać tych samych rachunków.

Element d[i] zapamiętujemy w zmiennej piwot, a do d[i] zapisujemy ostatni element partycji. Dzięki tej operacji piwot został usunięty ze zbioru.

Ustawiamy zmienną j na początek partycji. Zmienna ta zapamiętuje pozycję podziału partycji.

W pętli sterowanej zmienną i przeglądamy kolejne elementy od pierwszego do przedostatniego (ostatni został umieszczony na pozycji piwotu, a piwot zapamiętany). Jeśli i-ty element jest mniejszy od piwotu, to trafia on na początek partycji - wymieniamy ze sobą elementy na pozycjach i-tej i j-tej. Po tej operacji przesuwamy punkt podziałowy partycji j.

Po zakończeniu pętli element z pozycji j-tej przenosimy na koniec partycji, aby zwolnić miejsce dla piwotu, po czym wstawiamy tam piwot. Zmienna j wskazuje zatem wynikową pozycję piwotu. Pierwotna partycja została podzielona na dwie partycje:

Sprawdzamy, czy partycje te obejmują więcej niż jeden element. Jeśli tak, to wywołujemy rekurencyjnie algorytm sortowania szybkiego przekazując mu granice wyznaczonych partycji. Po powrocie z wywołań rekurencyjnych partycja wyjściowa jest posortowana rosnąco. Kończymy algorytm.

W celach badawczych testujemy czas wykonania algorytmu sortowania szybkiego w środowisku opisanym we wstępie. Program testujący jest następujący:

// Program testujący czas sortowania dla
// danego algorytmu sortującego
//--------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie
//--------------------------------------

program TestCzasuSortowania;

uses Windows;

const
  NAZWA = 'Sortowanie szybkie';
  K1    = '-----------------------------------------------------------';
  K2    = '(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie';
  K3    = '------n---------tpo---------tod---------tpp---------tpk---------tnp';
  K4    = '-------------------------------------------------------------------';
  MAX_LN = 8; // określa ostatnie LN
  LN : array[1..8] of integer = (1000,2000,4000,8000,16000,32000,64000,128000);

var
  d         : array[1..128000] of real; // sortowana tablica
  n         : integer;                  // liczba elementów
  qpf,tqpc  : int64;                    // dane dla pomiaru czasu
  qpc1,qpc2 : int64;

// Tutaj umieszczamy procedurę sortującą tablicę d
//-------------------------------------------------------

procedure Sortuj_szybko(lewy, prawy : integer);
var
  i,j     : integer;
  piwot,x : real;
begin
  i := (lewy + prawy) div 2;
  piwot := d[i]; d[i] := d[prawy];
  j := lewy;
  for i := lewy to prawy - 1 do
    if d[i] < piwot then
    begin
      x := d[i]; d[i] := d[j]; d[j] := x;
      inc(j);
    end;
  d[prawy] := d[j]; d[j] := piwot;
  if lewy < j - 1  then Sortuj_szybko(lewy, j - 1);
  if j + 1 < prawy then Sortuj_szybko(j + 1, prawy);
end;

function Sort : extended;
begin
  QueryPerformanceCounter(addr(qpc1));
  Sortuj_szybko(1,n);
  QueryPerformanceCounter(addr(qpc2));
  Sort := (qpc2 - qpc1 - tqpc) / qpf;
end;

// Program główny
//---------------
var
  i,j,k               : integer;
  tpo,tod,tpp,tpk,tnp : extended;
  f                   : Text;
begin
  if QueryPerformanceFrequency(addr(qpf)) then
  begin
    QueryPerformanceCounter(addr(qpc1));
    QueryPerformanceCounter(addr(qpc2));
    tqpc := qpc2 - qpc1;

    assignfile(f,'wyniki.txt'); rewrite(f);

// Wydruk na ekran

    writeln('Nazwa: ',NAZWA);
    writeln(K1);
    writeln(K2);
    writeln;
    writeln(K3);

// Wydruk do pliku

    writeln(f,'Nazwa: ',NAZWA);
    writeln(f,K1);
    writeln(f,K2);
    writeln(f,'');
    writeln(f,K3);
    for i := 1 to MAX_LN do
    begin
      n := LN[i];

// Czas sortowania zbioru posortowanego

      for j := 1 to n do d[j] := j;
      tpo := Sort;

// Czas sortowania zbioru posortowanego odwrotnie

      for j := 1 to n do d[j] := n - j;
      tod := Sort;

// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na początku - średnia z 10 obiegów

      tpp := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := k;
        d[1] := random * n + 1;
        tpp += Sort;
      end;
      tpp /= 10;

// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na końcu - średnia z 10 obiegów

      tpk := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := k;
        d[n] := random * n + 1;
        tpk += Sort;
      end;
      tpk /= 10;

// Czas sortowania zbioru nieuporządkowanego - średnia z 10 obiegów

      tnp := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := random;
        tnp += Sort;
      end;
      tnp /= 10;

      writeln(n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
      writeln(f,n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
    end;
    writeln(K4);
    writeln(f,K4);
    writeln(f,'Koniec');
    closefile(f);
    writeln;
    writeln('Koniec. Wyniki w pliku WYNIKI.TXT');
  end
  else writeln('Na tym komputerze program testowy nie pracuje !');
  writeln;
  write('Nacisnij klawisz ENTER...'); readln;
end.

Otrzymane wyniki są następujące (dla komputera o innych parametrach wyniki mogą się różnić co do wartości czasów wykonania, dlatego w celach porównawczych proponuję uruchomić podany program na komputerze czytelnika):

Nazwa: Sortowanie szybkie
-----------------------------------------------------------
(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
   1000    0.000115    0.000118    0.000132    0.000136    0.000292
   2000    0.000222    0.000227    0.000270    0.000284    0.000616
   4000    0.000464    0.000479    0.000556    0.000569    0.001330
   8000    0.001058    0.001079    0.001216    0.001225    0.002825
  16000    0.002124    0.002185    0.002472    0.002549    0.006088
  32000    0.004593    0.004465    0.005211    0.005104    0.012763
  64000    0.009873    0.010195    0.010849    0.011224    0.027306
 128000    0.020037    0.021543    0.022796    0.022578    0.057542
-------------------------------------------------------------------
Koniec

(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)
(Arkusz kalkulacyjny Excel do wyznaczania wzrostu prędkości sortowania)

Analizując wyniki obliczeń w arkuszu kalkulacyjnym otrzymanych czasów sortowania dla algorytmu sortowania szybkiego wyciągamy następujące wnioski:

Cechy Algorytmu Sortowania Szybkiego
klasa złożoności obliczeniowej optymistyczna
klasa złożoności obliczeniowej typowa
klasa złożoności obliczeniowej pesymistyczna
Sortowanie w miejscu	TAK
Stabilność	NIE

Klasy złożoności obliczeniowej szacujemy następująco:

• optymistyczna - dla zbiorów uporządkowanych (z niewielką liczbą elementów nie na swoich miejscach) - na podstawie czasów t_po, t_pp, t_pk
• typowa - dla zbiorów o losowym rozkładzie elementów - na podstawie czasu t_np
• pesymistyczna - dla zbiorów posortowanych odwrotnie - na podstawie czasu t_od. W przypadku tego algorytmu sortowania nie jest to przypadek pesymistyczny.

Własności algorytmu
Algorytm	tpo	tod	tpp	tpk	tnp
Sortowanie szybkie

1. Wszystkie otrzymane czasy sortowania są proporcjonalne do iloczynu n log₂ n, wnioskujemy zatem, iż klasa złożoności obliczeniowej algorytmu sortowania szybkiego jest równa O(n log n).
2. Czasy sortowania dla poszczególnych przypadków są mniej więcej tego samego rzędu, zatem nie wystąpił tutaj przypadek pesymistyczny (zwróć uwagę na istotny fakt - to, co dla jednego algorytmu jest przypadkiem pesymistycznym, dla innego wcale nie musi takie być).
3. Czas sortowania zbiorów nieuporządkowanych jest wyraźnie dłuższy od czasów sortowania zbiorów uporządkowanych częściowo.
4. Czas sortowania zbioru uporządkowanego oraz uporządkowanego odwrotnie jest praktycznie taki sam.

Wzrost prędkości sortowania
Algorytmy	tpo	tod	tpp	tpk	tnp
Sortowanie przez scalanie Sortowanie szybkie
	dobrze	dobrze	dobrze	dobrze	brak

5. Otrzymane wyniki potwierdzają, iż algorytm sortowania szybkiego jest najszybszym algorytmem sortującym. Jednakże w przypadku ogólnym notujemy jedynie bardzo nieznaczny wzrost prędkości sortowania w stosunku do algorytmu sortowania przez scalanie.

6. Ponieważ jak dotąd algorytm sortowania szybkiego jest najszybszym algorytmem sortującym, do dalszych porównań czasów sortowania zastosujemy czasy uzyskane w tym algorytmie.

1. Spróbuj znaleźć przypadek pesymistyczny dla algorytmu sortowania szybkiego opisanego w tym rozdziale.
2. Przebadaj algorytmy sortowania szybkiego, w których piwot wybierany jest:

   1. Na początku partycji

   2. Na końcu partycji

   3. W miejscu losowym wewnątrz partycji

3. Dlaczego czasy sortowania zbioru uporządkowanego i uporządkowanego odwrotnie są prawie równe?
4. Uzasadnij, iż algorytm sortowania szybkiego nie posiada cechy stabilności.
5. Wyszukaj w Internecie informację na temat algorytmu Introsort.