#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;

/**
   Zamienia miejscami dwie liczby całkowite.
   @param x pierwsza liczba całkowita do zamiany
   @param y druga liczba całkowita do zamiany
*/
void swap(int& x, int& y)
{  
   int temp = x;
   x = y;
   y = temp;
}

/**
   Dzieli fragment tablicy na partycje
   @param a tablica do podziału na partycje
   @param from pierwszy indeks fragmentu dzielonego na partycje
   @param to ostatni indeks fragmentu dzielonego na partycje
   @return ostatni indeks pierwszej partycji
*/
int partition(int a[], int from, int to)
{
   int pivot = a[from];
   int i = from - 1;
   int j = to + 1;
   while (i < j)
   {
      i++; while (a[i] < pivot) { i++; }
      j--; while (a[j] > pivot) { j--; }
      if (i < j) { swap(a[i], a[j]); }
   }
   return j;
}

/**
   Sortuje fragment tablicy przy użyciu sortowania szybkiego.
   @param a tablica do posortowania
   @param from pierwszy indeks fragmentu do posortowania
   @param to ostatni indeks fragmentu do posortowania
*/
void quicksort(int a[], int from, int to)
{
   if (from >= to) { return; }
   int p = partition(a, from, to);
   quicksort(a, from, p);
   quicksort(a, p + 1, to);
}

/** 
   Wyświetla wszystkie elementy tablicy.
   @param a tablica do wyświetlenia
   @param size liczba elementów tablicy a
*/
void print(int a[], int size)
{  
   for (int i = 0; i < size; i++)
   {
      cout << a[i] << " ";
   }
   cout << endl;
}

int main()
{  
   srand(time(0));
   const int SIZE = 20;
   int values[SIZE];
   for (int i = 0; i < SIZE; i++)
   {
      values[i] = rand() % 100;
   }
   print(values, SIZE);
   quicksort(values, 0, SIZE - 1);
   print(values, SIZE);
   return 0;
}

