// nuovi concetti: algoritmo "quick sort"
#include <iostream>

using namespace std;

int X[] = {54,6,26,73,1,69,36,70,14,76,81,85,99,8,16,38,45};
int n = sizeof(X)/sizeof(int);

void mostra_sequenza(char intestazione[])
{
  cout << "\n" << intestazione;
  for (int i = 0; i < n; i++)
    cout << " " << X[i];
  cout << "\n";
}

void quick_sort(int primo, int ultimo)
{
  int temp;          // variabile temporanea per lo scambio
  if (primo < ultimo)
  {
    //prendiamo come pivot il primo elemento della sequenza
    int pivot = X[primo];
    int i = primo;
    int j = ultimo;
    while (i < j)
    {
      // cerca, partendo da sinistra, il primo elemento > pivot
      while (i < ultimo && X[i] <= pivot)
	i++;
      // cerca, partendo da destra, il primo elemento < pivot
      while (j > primo && X[j] >= pivot)
	j--;
      if (i < j) //scambio(X[i],X[j])
      {
	temp = X[i];
	X[i] = X[j];
	X[j] = temp;
      }

    }
    //scambio(X[j],X[primo])
    temp = X[primo];
    X[primo] = X[j];
    X[j] = temp;

    //applico ricorsivamente quick sort alle due parti
    quick_sort(primo, j-1);
    quick_sort(j+1, ultimo);
  }
}

int main(void) {
  mostra_sequenza("Sequenza da ordinare:\n");
  quick_sort(0,n-1);
  mostra_sequenza("Sequenza ordinata con 'quick sort':\n");
}