//Implementacja sortowanie szybkie(quicksort)
//na podstawie wykladu dr M. Slusarka
//AT
//rozwiazanie czesciowe

#include <iostream>
#include <iomanip> //potrzebne dla setw()
using namespace std;

const int N = 20; //rozmiar tablicy
typedef int Item;

//------------------------------------------------------------
//---Generowanie elementow tablicy A[L..R] liczbami losowymi
//---od najmnieszy do najwiekszy
//------------------------------------------------------------
void generuj_tablice(int A[], int L, int R, int najmniejszy, int najwiekszy)
{
  srand(time(0));
  for (int i = L; i <= R; i++)
    A[i] = rand() % (najwiekszy - najmniejszy + 1) + najmniejszy;
}
//---koniec generuj_tablice----

//---------------------------------------------------
//-----wypisywanie fragmentu tablicy od A[L] do A[R]
//---------------------------------------------------
void wypisz_tablice(int A[], int L, int R)
{
  for (int i = L; i <= R; i++)
    cout << setw(3) << A[i]; //setw wymaga <iomanip>
  cout << endl;
}
//------------koniec wypisz_tablice-----------

//----------------------------------
//zamiana dwoch elementów wartosciami
//-----------------------------------
void exch(Item &A, Item &B)
{
  Item tmp = A;
  A = B;
  B = tmp;
}
//--koniec exch---------

//-----------------------------------------------------
//podział tablicy na dwie częœci
//na elementy mniejsze z lewej strony
//i elementy wieksze z prawej strony wybranego elementu
//-----------------------------------------------------
int partition(Item a[], int L, int R)
{ // założenie: wartownik a[R+1] >= a[i], i=L,L+1,...,R
  int i = L;
  int j = R + 1;
  Item v = a[L];
  while (1)
  {
    while (a[++i] < v)
      ;
    while (a[--j] > v)
      ;
    if (i >= j)
      break;
    exch(a[i], a[j]);
  }
  exch(a[L], a[j]);
  return j;
}

//---koniec partition---------------------

//----------------------------------------
//Quicksort
//Sortuje fragment tablicy od a[L] do r[R]
//----------------------------------------
void quicksort(Item a[], int L, int R)
{
  if (L >= R)
    return;
  int p = partition(a, L, R);
  quicksort(a, L, p - 1);
  quicksort(a, p + 1, R);
}
//--------koniec quicksort

//-----------------
//Wyszukuje największy element fragmentu tablicy od A[L] do AR]
//
Item max(Item A[], int L, int R)
{
  Item max = A[L];

  for (int i = L; i <= R; i++)
  {
    if (A[i] > max)
    {
      max = A[i];
    }
  }
  return max;
}

int main()
{
  Item a[N + 1];
  generuj_tablice(a, 0, N - 1, 0, 99);
  cout << "Tablica do posortowana: \n";
  wypisz_tablice(a, 0, N - 1);
  a[N] = max(a, 0, N - 1); // wartownik
  quicksort(a, 0, N - 1);

  cout << "\nPosortowana tablica :\n";
  wypisz_tablice(a, 0, N - 1);
  system("PAUSE");
  return 0;
}