#include <stdio.h>
#define N 12

/* Semplice macro che inverte i valori di due variabili */
#define   inverti(x, y)    { int t; t = x; x = y; y = t; }
/* Macro che ordina due variabili */
#define   ordina(x, y)     if (x > y) inverti(x, y)
/* Macro che ordina tre variabili */
#define   ordina3(x, y, z) ordina(x, y); ordina(x, z); ordina(y, z)

int   trova_perno(int *sinistra, int *destra, int *ptr_perno);
int   *dividi(int *sinistra, int *destra, int perno);
void  quicksort(int *sinistra, int *destra);

/* Funzione che ordina l'intervallo specificato */
void quicksort(int *sinistra, int *destra) {
    int *p, perno;
    
    /* Individuiamo il valore perno e lo mettiamo in perno (se possibile) */
    if (trova_perno(sinistra, destra, &perno)) {
        /* 
            Muoviamo gli elementi nell'array in modo che a sinistra di p
            risultino esserci solamente valori minori del valore perno, 
            maggiori o uguali a destra
        */
        p = dividi(sinistra, destra, perno);
        /* 
            Chiamiamo ricorsivamente quicksort sui due intervalli individuati
        */
        quicksort(sinistra, p - 1);
        quicksort(p, destra);
    }
}

/* Restituisce un valore che farà da perno, se possibile */
int trova_perno(int *sinistra, int *destra, int *ptr_perno) {
    int   a, b, c, *p;
    
    /* Prendiamo il primo, l'ultimo e l'elemento intermedio */
    a = *sinistra;
    b = *(sinistra + (destra - sinistra) / 2);
    c = *destra;
    /* Li ordiniamo in maniera crescente */
    ordina3(a, b, c);
    /* Se b non è uguale ad a lo prendiamo come elemento perno */
    if (a < b) {
        *ptr_perno = b;
        return 1;
    }
    /* Se c non è uguale a b lo prendiamo come elemento perno */
    if (b < c) {
        *ptr_perno = c;
        return 1;
    }
    
    /*
        Il primo, l'ultimo e l'elemento intermedio dell'array
        hanno tutti lo stesso valore: cerchiamo il primo con un 
        valore diverso a partire da sinistra 
    */
    for (p = sinistra + 1; p <= destra; ++p)
        if (*p != *sinistra) {
            *ptr_perno = (*p < *sinistra) ? *sinistra : *p;
            return 1;
        }
    /* 
        Tutti i valori dell'intervallo sono uguali, non è 
        possibile individuare un elemento perno
    */
    return 0;
}



/* 
    Divide l'intervallo specificato in due parti in modo che
    a destra di un certo elemento (viene determinato man mano
    e infine restituito) si trovino solamente valori maggiori
    o uguali al perno, a sinistra quelli minori.
    Per fare questo si parte dagli estremi dell'intervallo
    e ci si avvicina al centro lasciando immutati i valori
    minori del perno procedendo da sinistra e quelli maggiori
    o uguali al perno procedendo da destra, mentre si 
    invertono gli altri: ad esempio se il perno è 6 nella 
    sequenza 1 2 7 8 9 3 verranno scambiati di posizione il
    7 (primo elemento maggiore del perno a partire da sinistra)
    e il 3 (primo elemento minore del perno a partire da 
    destra). L'operazione viene ripetuta finché il puntatore
    di destra e quello di sinistra non si incontrano.
*/
int *dividi(int *sinistra, int *destra, int perno) {
    /* Finché i due puntatori non si incontrano */
    while (sinistra <= destra) {
        /*
            Individuiamo il primo elemento a partire
            da sinistra maggiore o uguale al perno
        */
        while (*sinistra < perno)
            ++sinistra;
        /*
            Individuiamo il primo elemento a partire
            da destra minore del perno
        */
        while (*destra >= perno)
            --destra;
        /* Se i due punti non coincidono */
        if (sinistra < destra) {
            /* Invertiamo le posizioni dei due valori */
            inverti(*sinistra, *destra);
            ++sinistra;
            --destra;
        }
    }
    /*
        Restituisce il puntatore all'elemento che divide
        l'intervallo secondo il criterio del perno
    */
    return sinistra;
}


int main(int argc, char *argv[]) {
    /* Un array composto da una sequenza di 12 valori casuali */
    int array[N] = {4,56,8,-2,5,-7,8,3,0,2,7,-1};
    int c1; /* Un contatore per stampare l'array */
    /* Stampiamo l'array prima dell'ordinamento */
    for (c1=0; c1 < N; c1++)
        printf("%d ", array[c1]);
    printf("\n");
    
    /* Ordiniamo l'array */
    quicksort(array, array + N - 1);
    
    /* Stampiamo l'array dopo l'ordinamento */
    for (c1=0; c1 < N; c1++)
        printf("%d ", array[c1]);
    printf("\n");
    
    return 0;
}