/* FILE: quickSort.cpp   last change: 12-Mar-2001
 * Ordinamento di un vettore utilizzando l'algoritmo QuickSort.
 */

#include <iostream.h>
#include <stdlib.h>


#define SIZE  10

void quicksort(int v[], int l, int r);
void swap(int *x, int *y);


main() {
  int i;

  int a[SIZE];		// Vettore contenente SIZE interi da ordinare

  // Inizializza il vettore caricando dei numeri casuali
  // e stampiamo il suo valore.
  cout << "Il vettore assegnato e`: " << endl;
  for (i = 0; i < SIZE; i++) {
    a[i] = rand();
    cout << "a[" << i << "]:" << a[i] << endl;
  }

  // Chiamiamo QuickSort su tutto il vettore
  quicksort(a, 0, SIZE - 1);

  // Stampiamo il risultato
  cout << "Il vettore ordinato e`: " << endl;
  for (i = 0; i < SIZE; i++)
    cout << "a[" << i << "]:" << a[i] << endl;
}



// Dato un vettore v, si considerano gli elementi compresi fra l'indice l e
// l'indice r.
void quicksort(int v[], int l, int r) {
  if (r > l) {	// C'e` almeno un elemento nel segmento considerato
    int pivot = v[r];	// Il pivot e` l'elemento piu` a destra
    int i = l - 1;
    int j = r - 1;


    // Alla fine del loop seguente ho tutti gli elementi minori del pivot a
    // sinistra e tutti quelli maggiori a destra
    for (;;) {
      // Scorro il vettore verso destra (trovo sicuramente il pivot)
      while (v[++i] < pivot);
      // Scorro il vettore verso sinistra
      while ((v[j] > pivot) && (--j >= 0));

      if (i < j)
	// Scambio l'elemento di posto i con quello di posto j
	swap(&v[i], &v[j]);
      else
	break;
    }
    swap(&v[i], &v[r]);

    quicksort(v, l, i - 1);	// Ordina il lato sinistro
    quicksort(v, i + 1, r);	// Ordina il lato destro
  }
}


// La funzione swap scambia il contenuto di due variabili
void swap(int *x, int *y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}