#include <vector>

using namespace std;

/**
   Sortuje kolumnę przy użyciu sortowania przez wstawianie.
   @param a tablica do posortowania
   @param size rozmiar tablicy a
   @param k indeks pierwszego elementu kolumny
   @param c odstęp między elementami kolumny
*/
void insertion_sort(int a[], int size, int k, int c)
{
   for (int i = k + c; i < size; i = i + c)
   {
      int next = a[i];
      // Przenieś wszystkie większe elementy dalej.
      int j = i;
      while (j >= c && a[j - c] > next)
      {
         a[j] = a[j - c];
         j = j - c;
      }
      // Wstaw element.
      a[j] = next;
   }
}

/**
   Sortuje tablicę przy użyciu sortowania Shella.
   @param a tablica do posortowania
   @param size rozmiar tablicy a
*/
void shell_sort(int a[], int size)
{  
   // Wygeneruj wartości ciągu odstępów.
   vector<int> columns;
   int c = 1;
   while (c < size) 
   { 
      columns.push_back(c);
      c = 3 * c + 1;          
   }

   // Dla każdego odstępu między kolumnami posortuj wszystkie .
   for (int s = columns.size() - 1; s >= 0; s--)
   {
      c = columns[s];
      for (int k = 0; k < c; k++)
      {
         insertion_sort(a, size, k, c);
      }         
   }
}

