Programma C ++ - Ricorsione

* 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