Sortowanie introspektywne

Sortowanie introspektywne (ang. introspective sort lub introsort) – odmiana sortowania hybrydowego, w której wyeliminowany został problem złożoności O(n²) występującej w najgorszym przypadku algorytmu sortowania szybkiego.

Sortowanie Hybrydowe

Pomysł Sortowania Hybrydowego opiera się na spostrzeżeniu, że ogromna liczba rekurencyjnych wywołań algorytmu Quick Sort jest realizowana dla małych tablic. W przypadku małych tablic czynności organizacyjne dokonywane przez procedurę Partition, takie jak wyznaczenie mediany z trzech, przygotowanie wskaźników i sprawdzanie warunków na nie nakładanych, zajmują relatywnie dużo czasu w stosunku do rozmiaru samej tablicy. Poza tym, samo wywołanie rekurencyjne jest czasochłonne i zajmuje miejsce na stosie, a dla 5-elementowej tablicy mogą być potrzebne nawet 3 wywołania. Dlatego też w algorytmie Sortowania Hybrydowego przyjęto, że małe tablice będą sortowane jednym z elementarnych algorytmów sortowania, które chociaż mają kwadratową złożoność obliczeniową, dla zbiorów o niewielkim rozmiarze działają relatywnie szybko. Opisana metoda nazywana jest „odcinaniem małych podzbiorów” i realizowana jest w ten sposób, że warunkiem wywołania rekurencyjnego procedury Quick Sort jest rozmiar tablicy większy od pewnej ustalonej wartości, eksperymentalnie wyznaczonej na 9.

Po zakończeniu rekurencyjnych wywołań procedury Quick Sort tablica podzielona jest na szereg małych podzbiorów o rozmiarze nie większym niż 9, porozdzielanych elementami, które w rekurencyjnych wywołaniach procedury Quick Sort wykorzystywane były jako elementy osiowe. Dla każdego takiego podzbioru prawdą jest, że klucz żadnego z jego elementów nie jest mniejszy od klucza jakiegokolwiek elementu poprzedzającego zbiór w tablicy ani nie jest większy od klucza jakiekolwiek elementu po nim następującego. Dla prawie posortowanej tablicy wywołuje się wówczas procedurę Sortowania Przez Wstawianie, której zadaniem jest uporządkowanie zbioru do końca. Sortowanie Przez Wstawianie jest elementarnym algorytmem sortowania, ale posiada liniową złożoność obliczeniową dla uporządkowanych tablic danych, ponieważ każdy kolejny element jest przepychany do przodu tablicy do momentu natrafienia na element od niego mniejszy. Jeśli tablica jest podzielona na podzbiory w taki sposób, jak opisano powyżej, to elementy każdego podzbioru będą porównywane tylko ze sobą.

Sortowanie Introspektywne

Głównym założeniem algorytmu Sortowania Introspektywnego jest obsługa najgorszego przypadku algorytmu Sortowania Szybkiego tak, aby zapewnić logarytmiczno-liniową złożoność obliczeniową. Przypomnijmy, że w najgorszym przypadku podziały wykonywane przez procedurę Partition były zdegenerowane i algorytm Quick Sort wykonywał O(n²) porównań.

Rozwiązaniem problemu złożoności obliczeniowej O(n²) w najgorszym przypadku jest badanie głębokości rekurencji. W procedurze głównej Sortowania Introspektywnego: Hybrid Introspective Sort tworzona jest stała M o wartości 2∙log₂n, która określa maksymalną dozwoloną głębokość wywołań rekurencyjnych. Następnie wywoływana jest procedura Intro Sort. Procedura Intro Sort przyjmuje jako dodatkowy parametr wartość M, która określa maksymalną dozwoloną głębokość wywołań rekurencyjnych z poziomu, na którym obecnie się znajdujemy. Jeżeli wartość parametru M wynosi 0, wywołania rekurencyjne są kończone i dla podproblemu, którym obecnie się zajmujemy, wywoływana jest procedura Sortowania Przez Kopcowanie, które jest traktowane jako sortowanie pomocnicze.

W przypadku gdy M > 0 procedura Intro Sort działa podobnie jak procedura Quick Sort. Wywoływana jest procedura Partition, która dzieli tablicę na dwa rozłączne podzbiory, gromadząc w pierwszym elementy posiadające klucze o wartości mniejszej równej wartości klucza elementu rozdzielającego, a w drugim elementy o wartościach kluczy większych równych kluczowi pivota. Następnie dla obu podzbiorów wywołana jest rekurencyjnie procedura Intro Sort z parametrem M pomniejszonym o 1, w związku z czym maksymalna dozwolona głębokość rekurencyjnych wywołań z następnego poziomu jest o 1 mniejsza.

Dzięki zastosowanej procedurze otrzymujemy gwarancję, że w najgorszym przypadku algorytmu Sortowania Szybkiego (sekwencja Median-Of-Three killer) po zrealizowaniu 2∙log₂n zdegenerowanych podziałów rekurencja zostanie zatrzymana i wywołana zostanie procedura sortowania pomocniczego Heap Sort, którego złożoność obliczeniowa wynosi O(n∙log₂n). Dla losowych danych Sortowanie Przez Kopcowanie działa około 3 razy dłużej niż Sortowanie Szybkie, zauważmy jednak, że dozwolona głębokość wywołań rekurencyjnych 2∙log₂n przekracza głębokość rekurencji w średnim przypadku, czyli około 1,39∙log₂n. Dzięki temu dla danych losowych Sortowanie Introspektywne będzie działało tak samo jak Sortowanie Szybkie z odcinaniem małych podzbiorów, a Sortowanie Przez Kopcowanie jako sortowanie pomocnicze wywoływane będzie tylko wówczas, gdy przynajmniej początkowe podziały będą zdegenerowane.

Listing procedury Hybrydowego Sortowania Introspektywnego w języku C

template <class Item>
void Hybrid_Introspective_Sort (Item *Array, long N)
{
  IntroSort(Array,N,(int)floor(2*log(N)/M_LN2));
  Insertion_Sort(Array,N);
}
 
template <class Item>
void IntroSort (Item *Array, long N, int M)
{
  long i;
  if (M<=0)
  {
    Heap_Sort(Array,N);
    return;
  }
  i=Partition(Array,0,N);
  if (i>9)
    IntroSort(Array,i,M-1);
  if (N-1-i>9)
    IntroSort(Array i 1,N-1-i,M-1);
}

Kod procedury Partition jest taki sam, jak w przypadku sortowania szybkiego:

template <class Item>
long Partition (Item *Array, long L, long R)
{
  long i, j;
  if (R>=3)
    MedianOfThree(Array,L,R);
  for (i=L, j=R-2; ; )
  {
    for ( ; Array[i]<Array[R-1];   i);
    for ( ; j>=L && Array[j]>Array[R-1]; --j);
    if (i<j)
      Exchange(Array,i  ,j--);
    else break;
  }
  Exchange(Array,i,R-1);
  return i;
}
 
template <class Item>
void MedianOfThree (Item *Array, long &L, long &R)
{
  if (Array[  L-1]>Array[--R])
    Exchange(Array,L-1,R);
  if (Array[L-1]>Array[R/2])
    Exchange(Array,L-1,R/2);
  if (Array[R/2]>Array[R])
    Exchange(Array,R/2,R);
  Exchange(Array,R/2,R-1);
}
 
template <class Item>
void Exchange (Item *Array, long i, long j)
{
  Item temp;
  temp=Array[i];
  Array[i]=Array[j];
  Array[j]=temp;
}

Kod procedury Heap Sort to kod sortowania przez kopcowanie:

template <class Item>
void Heap_Sort (Item *Array, long N)
{
  long i;
  for (i=N/2; i>0; --i)
    Heapify(Array-1,i,N);
  for (i=N-1; i>0; --i)
  {
    Exchange(Array,0,i);
    Heapify(Array-1,1,i);
  }
}
 
template <class Item>
void Heapify (Item *Array, long i, long N)
{
  long j;
  while (i<=N/2)
  {
    j=2*i;
    if (j 1<=N && Array[j 1]>Array[j])
      j=j 1;
    if (Array[i]<Array[j])
      Exchange(Array,i,j);
    else break;
    i=j;
  }
}

Procedura Insertion Sort to procedura sortowania przez wstawianie:

template <class Item>
void Insertion_Sort (Item *Array, long N)
{
  long i, j;
  Item temp;
  for (i=1; i<N;   i)
  {
    temp=Array[i];
    for (j=i; j>0 && temp<Array[j-1]; --j)
      Array[j]=Array[j-1];
    Array[j]=temp;
  }
}

Złożoność obliczeniowa, najlepszy i najgorszy przypadek algorytmu

W przypadku ogólnym, a więc również w najgorszym, algorytm Sortowania Introspektywnego posiada złożoność obliczeniową O(n∙log₂n).

W najgorszym przypadku algorytm wykonuje najpierw M=2∙log₂n rekurencyjnych wywołań, takich jak w Sortowaniu Szybkim, a następnie dla pozostałego podzbioru wywołuje procedurę Heap Sort. Tak więc w najgorszym przypadku dane na pozycjach o indeksach: 0, od N/2–M do N/2 i od N/2–2∙M do N muszą być ustawione w sekwencji Median-Of-Three killer, a dane na pozostałych pozycjach muszą stanowić zły przypadek dla algorytmu Heap Sort, na przykład być posortowane. W takiej sytuacji algorytm wykona około 4∙n∙log₂n n–6∙(log₂n)² operacji porównywania danych.

W najlepszym i pośrednim przypadku jednak algorytm Sortowania Introspektywnego działa tak samo, jak algorytm Sortowania Szybkiego, stąd można wywnioskować, że w najlepszym przypadku dla danych posortowanych wykonywanych będzie około n∙log₂n porównań, a dla danych losowych około 1,39∙n∙log₂n porównań.

Algorytm Sortowania Introspektywnego potrzebuje O(log₂n) pamięci na stos w każdym przypadku i jest algorytmem sortującym w miejscu.