#include <stdio.h>
#include <stdlib.h>     // rand() et srand()
#include <time.h>       // time()
#if ! defined( _WIN32) && ! defined( __TURBOC__)
#include <unistd.h>     // read()
#else
#include <conio.h>
#endif

static void swap( int *pa, int *pb )
{
    int t = *pa;
    *pa = *pb;
    *pb = t;
}

static int  prepare_quick_sort( int * tab, int debut, int fin, int val_pivot )
{
    int pos_pivot = debut;

    while( debut < fin )
    {
        // On s'arrete quand on a trouve une valeur
        // superieure a val_pivot
        while( tab[debut] < val_pivot ) debut ++;

        // On s'arrete quand on a trouve une valeur
        // inferieure a val_pivot
        while( tab[fin] > val_pivot ) fin --;

        // On echange les valeurs
        if( debut < fin )
        {
            swap( &tab[debut], &tab[fin] );
        }

        // On se mefie des valeurs identiques
        if( debut != fin && tab[debut] == tab[fin] )
        {
            debut ++;
	}
    }

    // La position du pivot est en fait l'indice de fin
    pos_pivot = fin;

    return pos_pivot;
}

void quick_sort( int * tab, int debut, int fin )
{
    // On utilise comme pivo la premiere valeur
    int val_pivot = tab[debut];
    int pos_pivot;    
  
    // Condition de sortie
    if( debut >= fin ) return;
    
    // On separe le tableau en 2 parties :
    // On met les valeurs inferieures a val_pivot au debut
    // On met les valeurs superieures a val_pivot a la fin
    // On renvoie la position finale de la valeur val_pivot
    pos_pivot = prepare_quick_sort( tab, debut, fin, val_pivot );

    // On trie chaque liste
    if( pos_pivot == fin )
    {
        // Ca veut dire que le pivot se retrouve a la fin
        // on evite de traiter en boucle la meme liste
        pos_pivot --;
    }
    if( pos_pivot != fin )
    {
        quick_sort( tab, debut, pos_pivot );
    }
    if( pos_pivot + 1 != debut )
    {
        quick_sort( tab, pos_pivot + 1, fin );    
    }
}


static int get_tab_len()
{
    int len = 0;
    while( len <= 0 )
    {
        scanf( "%d", &len );
    }
    return len;
}

static int get_random_value( int max )
{
    static int s_first = 1;
    if( s_first )
    {
        srand( time(NULL) );
        s_first = 0;
    }
    return rand() % max;
}

static void remplit_tableau( int * tab, int len )
{
    for( int i = 0; i < len; i ++ )
    {
        tab[i] =  get_random_value( 100 );
    }
}

static void affiche_tab( int * tab, int len )
{
    for( int i = 0; i < len; i ++ )
    {
        printf( "tab[%d] = %d\n", i, tab[i] );
    }
}

static int  verif_tableau_ordonne( int * tab, int len )
{
    int ret = 0;
    for( int i = 1; i < len; i ++ )
    {
        if( tab[i-1] > tab[i] )
        {
            printf( "Erreur: Tableau mal ordonne "
                    "(i=%d, tab[i-1]=%d > tab[i]=%d\n", 
                    i, tab[i-1], tab[i] );
            ret = -1;
        }
    }
    return ret;
}

#if ! defined( _WIN32) && ! defined( __TURBOC__)
int getch()
{
    char buf[10];
    read( 0, buf, 10 );
    return buf[0];
}
#endif


int main()
{
    int * tab = NULL;
    int len;

    printf( "Taille du tableau :\n" );
    len = get_tab_len();
    tab = (int *)malloc( len * sizeof(int) );
    if( tab == NULL ) return -1;
    remplit_tableau( tab, len );
        
    printf( "\nAffichage du tableau non trie (%d elements)\n", len );
    affiche_tab( tab, len );
    getch();

    quick_sort( tab, 0, len-1 );    
    printf( "\nAffichage du tableau trie (%d elements)\n", len );
    affiche_tab( tab, len );
    verif_tableau_ordonne( tab, len );
    getch();
    free( tab );
    return 0;
}