class Partition_debug {

    static void remplissage_aleat (int[] t) {
        for (int i=0; i<t.length; i++)
            t[i] = (int) (Math.random() * 10); 
    }

    static void affichage2 (int[] t, int i, int j) {
        if (i<=j) {
            System.out.print(t[i] + " ");
            affichage2(t, i+1, j);
        }
    }

    static void affichage (int[] t) {
        affichage2(t, 0, t.length-1);
        System.out.println();
    }

    static void quicksort (int[] t, int i, int j) {
        int indice_pivot;
        if (i<j) /* i=j : trie ; i>j : appel hors domaine de definition */ {
            indice_pivot = partition (t, i, j);
            quicksort(t, i, indice_pivot-1);
            quicksort(t, indice_pivot+1, j);
        }
    }

    static void aff (int g, int d) {
        for (int k=0; k<10; k++) 
            if (k==g || k==d) 
                System.out.print("* "); 
            else 
                System.out.print("  ");
        System.out.println(); 
    }


    static int partition (int[] t, int i, int j) {
        int pivot, g, d, tmp;

        pivot = t[i]; // variable pivot inutile techniquement mais plus lisible
        g = i+1;
        d = j;
        while (g<=d) { // cas = utile quand g d part et d'autre d'un grand 
                       // ex: 3 4 0 5 8 1 4 6 1 5
            while (g<=j && t[g]<=pivot) g++; // g pas borne en haut...
            while (d>i  && t[d]>pivot)  d--; // d borne en bas par pivot
                // 1. t[d]>pivot au lieu >= : 
                // ne pas laisser des copies du pivot a droite :
                // se voit dans test avec 2 occurences du pivot.
                // 2. d>i au lieu >= : >= inutile car d=i incompatible 
                // avec t[d]>pivot car pivot=t[i], autrement dit
                // d-i et t[d]>pivot jamais vrais ensemble
            if (g<d) {
                tmp = t[g];
                t[g] = t[d];
                t[d] = tmp;

aff(g,d);
System.out.println("-------------------");
affichage(t);

                g++;
                d--;
            }
        }
        t[i] = t[d];
        t[d] = pivot;
        return d;
    }

    static void main (String[] args) {

        int N=10;
        int[] s = new int[N];

        remplissage_aleat(s);
        affichage(s);
//        quicksort(s, 0, N-1);
        System.out.println(partition(s, 0, N-1));
        System.out.println("-------------------");
        affichage(s);
    }
}