/**
 * Cette classe effectue des opérations plus complexes sur un tableaux d'entiers : recherche dichotomique, tris, etc.
 * La taille d'un tableau est par définition le nombre TOTAL de cases = tab.length.
 * Un tableau d'entiers créé possède nbElem élements qui ne correspond pas forcément à la taille du tableau.
 * Il faut donc toujours considéré que nbElem <= tab.length (= taille).
 * Il est fait usage de la classe SimplesTableau pour accéder aux méthodes de cette classe.
 * @author Grégoire MAROUSE - novembre 2024
 */
class TrisTableau {
    /*Variable globale, compteur du nombre d'opérations*/
    long cpt=0;
    /*Variable globale permettant l'accès aux méthodes de la classe SimplesTableau */
    SimplesTableau monSpleTab = new SimplesTableau();



    /* notes :
        System.currentTimeMillis() ou System.currentTimeMillis()
        lognA = log10A / log10n (utiliser Math.log10 ( double d ) de Java quirenvoie un type double).
    */



    /**
     * Le point d'entrée du programme.
     */
    void principal(){
        testRechercheSeq();
        testRechercheSeqEfficacite();
        testVerifTri();
        testRechercheDicho();
        testRechercheDichoEfficacite();
        testTriSimple();
        testTriSimpleEfficacite();
        testSeparer();
        testTriRapideRec();
        testTriRapide();
        testTriRapideEfficacite();
        testCreerTabFreq();
        testTriParComptageFreq();
        testTriParComptageFreqEfficacite();
        testTriABulles();
        testTriABullesEfficacite();
    }



    /**
     * Recherche séquentielle d'une valeur dans un tableau.
     * La valeur à rechercher peut exister en plusieurs exemplaires mais la recherche s'arrête dès qu'une première valeur est trouvée.
     * On suppose que le tableau passé en paramètre est créé et possède au moins une valeur (nbElem > 0).
     * Ceci ne doit donc pas être vérifié.
     * @param leTab  - le tableau dans lequel effectuer la recherche
     * @param nbElem  - le nombre d'entiers que contient le tableau
     * @param aRech  - l'entier à rechercher dans le tableau
     * @return l'indice (>=0) de la position de l'entier dans le tableau ou -1 s'il n'est pas présent
     */
    int rechercheSeq(int[] leTab, int nbElem, int aRech){
        // variables locales
        int res=-1; //2op
        int i ; // 1 op
        // initialisations
        i = 0; // 1 op
        while ( i < nbElem && res==-1) { // 3 op
            if ( aRech == leTab[i] ) { // 1 op
                res=i;
            }
            cpt++;
            i++; // 2 op
        }
        return res;
    }

    /**
     * test de rechercheSeq()
     */
    void testRechercheSeq(){
        System.out.println("\n*** Test de rechercheSeq()");
        System.out.println("** Cas normaux");
        testCasRechercheSeq(new int[]{0,1,2,3,4,5,6,7},8,5,5);
        testCasRechercheSeq(new int[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},15,1,14);
        testCasRechercheSeq(new int[]{1,12,8,4,7,6,3,5,5,6,8,9,7,13},14,6,5);

        System.out.println("** Cas limites");
        testCasRechercheSeq(new int[1],1,0,0);
        testCasRechercheSeq(new int[5],5,0,0);

        System.out.println("** Cas d'erreurs");
        testCasRechercheSeq(new int[10],10,1,-1);
        testCasRechercheSeq(new int[1],1,1,-1);
    }

    /**
     * Test un Cas d'appel de rechercheSeq()
     * @param leTab  - le tableau dans lequel effectuer la recherche
     * @param nbElem  - le nombre d'entiers que contient le tableau
     * @param aRech  - l'entier à rechercher dans le tableau
     */
    void testCasRechercheSeq(int[] leTab, int nbElem, int aRech, int result){
        // Affichage
		System.out.print ("rechercheSeq (");
        monSpleTab.afficherTab(leTab,leTab.length);
		System.out.print (", "+nbElem+", "+aRech+") \t= " + result + "\t : ");
		// Appel
		int resExec = rechercheSeq(leTab, nbElem, aRech);
		// Verification
		if (resExec == result){
			System.out.println ("OK");
		} else {
			System.err.println ("ERREUR");
		}
    }

    /**
     * test de l'éfficacité de rechercheSeq()
     */
    void testRechercheSeqEfficacite() { //0(n)
        System.out.println("** Test de l'éfficacité");
        for (int i=8000000; i<=1024000000; i*=2){
            cpt = 0;
            int[] tab = new int[i];
            tab[i-1]=1;
            long debut = System.currentTimeMillis();
            rechercheSeq(tab, i, 1);
            long fin = System.currentTimeMillis();
            long temps=fin-debut;
            double cst=cpt/(double)i;
            System.out.println("n="+i+"\t\ttemps="+temps+"\t\tcompteur="+cpt+"\t\tconstante1="+cst);
        }
    }



    /**
     * Vérifie que le tableau passé en paramètre est trié par ordre croissant des valeurs.
     * On suppose que le tableau passé en paramètre est créé et possède au moins une valeur (nbElem > 0).
     * Ceci ne doit donc pas être vérifié.
     * @param leTab - le tableau à vérifier (trié en ordre croissant)
     * @param nbElem - le nombre d'entiers présents dans le tableau
     * @return true si le tableau est trié sinon false
     */
    boolean verifTri(int[] leTab, int nbElem){
        boolean trie = true;
        int i =0;
        while(i<nbElem-1 && trie){
            if(leTab[i]>leTab[i+1]){
                trie = false;
            }
            i++;
        }

        return trie;
    }

    /**
     * Test de verifTri()
     */
    void testVerifTri(){
        System.out.println("\n*** Test de verifTri()");
        System.out.println("** Cas normaux");
        testCasVerifTri(new int[] {1,2,3,3,5,6,666},0,true);
        testCasVerifTri(new int[] {2,1,2,3,4,5,6,7,8,9,10,11,12},12,false);
        testCasVerifTri(new int[] {1,2,3,4,5,6,7,8,10,9,7,5,1},8,true);

        System.out.println("** Cas limites");
        testCasVerifTri(new int[10],10,true);
        testCasVerifTri(new int[]{5},1,true);
    }

    /**
     * Test un Cas d'appel de verifTri()
     * @param leTab - le tableau à vérifier (trié en ordre croissant)
     * @param nbElem - le nombre d'entiers présents dans le tableau
     * @param result - le résultat attendu
     */
    void testCasVerifTri(int[] leTab, int nbElem, boolean result){
        // Affichage
        System.out.print ("verifTri (");
        monSpleTab.afficherTab(leTab,leTab.length);
        System.out.print (", "+nbElem+") \t= " + result + "\t : ");
        // Appel
        boolean resExec = verifTri(leTab, nbElem);
        // Verification
        if (resExec == result){
            System.out.println ("OK");
        } else {
            System.err.println ("ERREUR");
        }
    }



    /**
     * Recherche dichotomique d'une valeur dans un tableau.
     * On suppose que le tableau est trié par ordre croissant.
     * La valeur à rechercher peut exister en plusieurs exemplaires, dans ce cas, c'est la valeur à l'indice le + faible qui sera trouvé.
     * On suppose également que le tableau passé en paramètre est créé et possède au moins une valeur (nbElem > 0).
     * Ceci ne doit donc pas être vérifié.
     * @param leTab - le tableau trié par ordre croissant dans lequel effectuer la recherche
     * @param nbElem - le nombre d'entiers que contient le tableau
     * @param aRech - l'entier à rechercher dans le tableau
     * @return l'indice (>=0) de la position de l'entier dans le tableau ou -1 s'il n'est pas présent
     */
    int rechercheDicho(int[] leTab, int nbElem, int aRech){
        int indD, indF, indM, ret; // 4 op
        indD = 0; // 1 op
        indF = nbElem - 1; // 2 op
        while ( indD != indF ) { // 1 op
            indM = ( indD + indF ) / 2; // 3 op
            if ( aRech > leTab[indM] ) { // 1 op
                indD = indM + 1; // 2 op
            } else indF = indM; // 1 op
            cpt++;
        }
        if ( aRech == leTab [indD] ) ret = indD; // 2 op
        else ret = -1; // 1 op
        return ret;
    }

    /**
     * Test de rechercheDicho()
     */
    void testRechercheDicho(){
        System.out.println("\n*** Test de rechercheDicho()");
        System.out.println("** Cas normaux");
        testCasRechercheDicho(new int[]{0,1,2,3,4,5,6,7},8,5,5);
        testCasRechercheDicho(new int[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},15,1,14);
        testCasRechercheDicho(new int[]{-5,-1,0,1,1,2,6,6,6,7,9,13,16,22},12,6,6);

        System.out.println("** Cas limites");
        testCasRechercheDicho(new int[1],1,0,0);
        testCasRechercheDicho(new int[5],5,0,0);

        System.out.println("** Cas d'erreurs");
        testCasRechercheDicho(new int[10],10,1,-1);
        testCasRechercheDicho(new int[1],1,1,-1);
    }

    /**
     * Test un Cas d'appel de rechercheDicho()
     * @param leTab - le tableau à vérifier (trié en ordre croissant)
     * @param nbElem - le nombre d'entiers présents dans le tableau
     * @param aRech - l'entier à rechercher dans le tableau
     * @param result - le résultat attendu
     */
    void testCasRechercheDicho(int[] leTab, int nbElem, int aRech, int result){
        // Affichage
        System.out.print ("rechercheDicho (");
        monSpleTab.afficherTab(leTab,leTab.length);
        System.out.print (", "+nbElem+", "+aRech+") \t= " + result + "\t : ");
        // Appel
        int resExec = rechercheDicho(leTab, nbElem, aRech);
        // Verification
        if (resExec == result){
            System.out.println ("OK");
        } else {
            System.err.println ("ERREUR");
        }
    }

    /**
     * Test de l'efficacité de rechercheDicho()
     */
    void testRechercheDichoEfficacite() { //0(log2n)
        System.out.println("** Test de l'éfficacité");
        for (int i=1000000; i<=124000000; i*=2){
            cpt = 0;
            int[] tab = new int[i];
            long debut = System.currentTimeMillis();
            rechercheDicho(tab, i, 1);
            long fin = System.currentTimeMillis();
            long temps=fin-debut;
            double cst=cpt/(Math.log10(i)/Math.log10(2));
            System.out.println("n="+i+"\t\ttemps="+temps+"\t\tcompteur="+cpt+"\t\tconstante2="+cst);
        }
    }



    /**
     * Tri par ordre croissant d'un tableau selon la méthode simple : l'élément minimum est placé en début de tableau (efficacité en n carré).
     * On suppose que le tableau passé en paramètre est créé et possède au moins une valeur (nbElem > 0).
     * Ceci ne doit donc pas être vérifié.
     * @param leTab - le tableau à trier par ordre croissant
     * @param nbElem - le nombre d'entiers que contient le tableau
     */
    void triSimple(int[] leTab, int nbElem){
        // variables locales
        int i, p, k, min;
        // première boucle = celle qui parcourt le tableau de 0
        // à (n – 2) y compris
        for ( i = 0; i <= (nbElem-2); i++ ) {
            // sélectionner la + petite valeur sur le sous-tableau
            // allant de i à (n-1) : on identifie une case « k »
            min = leTab[i];
            k = i;
            for ( p=(i+1); p <= (nbElem-1); p++ ) {
                if ( leTab[p] < min ) {
                    min = leTab[p];
                    k = p;
                }
                cpt++;
            }
            // ensuite échanger cette case « k » avec « i »
            monSpleTab.echange(leTab,nbElem,k,i);
        }
    }

    /**
     * Test de triSimple()
     */
    void testTriSimple(){
        System.out.println("\n*** Test de triSimple()");
        System.out.println("** Cas normaux");
        testCasTriSimple(new int[] {0,1,2,3,4,5,2,7,6},6);
        testCasTriSimple(new int[] {-2,35,1,68,8,64,1,3,21,8},10);

        System.out.println("** Cas limites");
        testCasTriSimple(new int[5],5);
        testCasTriSimple(new int[] {-8},1);
    }

    /**
     * Test un Cas d'appel de triSimple()
     * @param leTab - le tableau à vérifier (trié en ordre croissant)
     * @param nbElem - le nombre d'entiers présents dans le tableau
     */
    void testCasTriSimple(int[] leTab, int nbElem){
        // Affichage
        System.out.print ("triSimple (");
        monSpleTab.afficherTab(leTab,leTab.length);
        System.out.print (", "+nbElem+") \t= ");
        // Appel
        triSimple(leTab, nbElem);
        boolean trie = verifTri(leTab, nbElem);

        monSpleTab.afficherTab(leTab,nbElem);
        System.out.print("\t : ");
        // Verification
        if (trie == true){
            System.out.println ("OK");
        } else {
            System.err.println ("ERREUR");
        }
    }

    /**
     * Test de l'efficacité de triSimple()
     */
    void testTriSimpleEfficacite(){ //0(n²)
        System.out.println("** Test de l'éfficacité");
        for (int i=4000; i<=64000; i*=2){
            cpt = 0;
            int[] tab = new int[i];
            for(int j =0; j<tab.length; j++){
                tab[j]=i-j;
            }
            long debut = System.currentTimeMillis();
            triSimple(tab,i);
            long fin = System.currentTimeMillis();
            long temps=fin-debut;
            double cst=cpt/((double)i*i);
            System.out.println("n="+i+"\t\ttemps="+temps+"\t\tcompteur="+cpt+"\t\tconstante3="+cst);
        }
    }



    /**
     * Cette méthode renvoie l’indice de séparation du tableau en 2 parties par placement du pivot à la bonne case.
     * @param tab - le tableau des valeurs
     * @param indR - indice Right de fin de tableau
     * @param indL - indice Left de début de tableau
     * @return l’indice de séparation du tableau
     */
    int separer(int[] tab, int indL, int indR){
        boolean ok = indL>=0 && indR<tab.length && indL<=indR;
        while (ok && indL<indR){
            if(tab[indL]>tab[indL+1]){
                monSpleTab.echange(tab, tab.length, indL+1, indL);
                indL++;
            } else {
                monSpleTab.echange(tab, tab.length, indL+1, indR);
                indR--;
            }
        }
        if(!ok){
            System.out.println("\n separer() : Indices invalides");
            indR=-1;
        }
        return indR;
    }

    /**
     * Test de separer()
     */
    void testSeparer(){
        System.out.println("\n*** Test de separer()");
        System.out.println("** Cas normaux");
        testCasSeparer(new int[] {-2,0,1,4,7},0,4,0);
        testCasSeparer(new int[] {1,-5,7,8,9,1,5},0,6,1);

        System.out.println("** Cas limites");
        testCasSeparer(new int[5],2,2,2);
        testCasSeparer(new int[10],3,7,3);

        System.out.println("** Cas d'erreur");
        testCasSeparer(new int[10],5,12,-1);
    }

    /**
     * Test un Cas d'appel de separer()
     * @param tab - le tableau des valeurs
     * @param indR - indice Right de fin de tableau
     * @param indL - indice Left de début de tableau
     * @param result - le resultat attendu
     */
    void testCasSeparer(int[] leTab, int indL, int indR, int result){
        // Affichage
        System.out.print ("separer (");
        monSpleTab.afficherTab(leTab,leTab.length);
        System.out.print (", "+indL+", "+indR+") \t= " + result + "\t : ");
        // Appel
        int resExec = separer(leTab, indL, indR);
        // Verification
        if (resExec == result){
            System.out.println ("OK");
        } else {
            System.err.println ("ERREUR");
        }
    }



    /**
     * Méthode de tri récursive selon le principe de séparation.
     * La méthode s'appelle elle-même sur les tableaux gauche et droite par rapport à un pivot.
     * @param tab - le tableau sur lequel est effectué la séparation
     * @param indL - l'indice gauche de début de tableau
     * @param indR - l'indice droite de fin de tableau
     */
    void triRapideRec(int[] tab, int indL, int indR){
        int indice = separer(tab,indL,indR);
        if(indice!=-1){
            if (indice+1 < indR){
                triRapideRec(tab, indice+1, indR);
            }
            if (indice-1 > indL) {
                triRapideRec(tab, indL, indice-1);
            }
        }
        cpt++;
    }

    /**
     * Test un Cas d'appel de triRapideRec()
     */
    void testTriRapideRec(){
        System.out.println("\n*** Test de triRapideRec()");
        testCasTriRapideRec(new int[] {-2,0,1,4,7},0,4,new int[] {-2,0,1,4,7});
        testCasTriRapideRec(new int[] {1,-5,7,8,9,1,5},0,6,new int[] {-5,1,1,5,7,8,9});

        System.out.println("** Cas limites");
        testCasTriRapideRec(new int[5],2,2,new int[5]);
        testCasTriRapideRec(new int[10],3,7,new int[10]);

        System.out.println("** Cas d'erreur");
        testCasTriRapideRec(new int[10],5,12,new int[10]);
    }

    /**
     * Test un Cas d'appel de triRapideRec()
     * @param tab - le tableau des valeurs
     * @param indR - indice Right de fin de tableau
     * @param indL - indice Left de début de tableau
     * @param result - le resultat attendu
     */
    void testCasTriRapideRec(int[] leTab, int indL, int indR, int[] result){
        // Affichage
        System.out.print ("triRapideRec (");
        monSpleTab.afficherTab(leTab,leTab.length);
        System.out.print (", "+indL+", "+indR+") \t= ");
        // Appel
        triRapideRec(leTab, indL, indR);
        boolean ok = monSpleTab.egalite(result, leTab, result.length, leTab.length);

        monSpleTab.afficherTab(leTab,leTab.length);
        System.out.print("\t : ");
        // Verification
        if (ok){
            System.out.println ("OK");
        } else {
            System.err.println ("ERREUR");
        }
    }


    /**
     * Tri par ordre croissant d'un tableau selon la méthode du tri rapide (QuickSort).
     * On suppose que le tableau passé en paramètre est créé et possède au moins une valeur (nbElem > 0).
     * Ceci ne doit donc pas être vérifié.
     * Cette méthode appelle triRapideRec(...) qui elle effectue réellement le tri rapide selon la méthode de séparation récursive.
     * @param leTab - le tableau à trier par ordre croissant
     * @param nbElem - le nombre d'entiers que contient le tableau
     */
    void triRapide(int[] leTab, int nbElem){
        triRapideRec(leTab, 0, nbElem-1);
    }

    /**
     * Test de triRapide()
     */
    void testTriRapide(){
        System.out.println("\n*** Test de triRapide()");
        System.out.println("** Cas normaux");
        testCasTriRapide(new int[] {0,1,2,3,4,5,2,7,6},6);
        testCasTriRapide(new int[] {-2,35,1,68,8,64,1,3,21,8},10);

        System.out.println("** Cas limites");
        testCasTriRapide(new int[5],5);
        testCasTriRapide(new int[] {-8},1);
    }

    /**
     * Test d'un cas d'appel de triRapide()
     * @param leTab - le tableau des valeurs
     * @param nbElem - indice Right de fin de tableau
     * @param result - le resultat attendu
     */
    void testCasTriRapide(int[] leTab, int nbElem){
        // Affichage
        System.out.print ("triRapide (");
        monSpleTab.afficherTab(leTab,leTab.length);
        System.out.print (", "+nbElem+") \t= ");
        // Appel
        triRapide(leTab, nbElem);
        boolean trie = verifTri(leTab, nbElem);

        monSpleTab.afficherTab(leTab,nbElem);
        System.out.print("\t : ");
        // Verification
        if (trie == true){
            System.out.println ("OK");
        } else {
            System.err.println ("ERREUR");
        }  
    }

    
    /**
     * Test de l'efficacité de triRapide()
     */
    void testTriRapideEfficacite() { // Ɵ(nlog2n)
        System.out.println("** Test de l'éfficacité");
        //calcul
        for (int i=160000; i<=20480000; i*=2){
            cpt = 0;
            int[] tab = new int[i];
            monSpleTab.remplirAleatoire(tab, i, 0, 1000000);
            long debut = System.currentTimeMillis();
            triRapide(tab, i);
            long fin = System.currentTimeMillis();
            long temps=fin-debut;
            double cst=cpt/(i*Math.log10(i)/Math.log10(2));
            System.out.println("n="+i+"\t\ttemps="+temps+"\t\tcompteur="+cpt+"\t\tconstante4="+cst);
        }
    }



    /**
     * A partir d'un tableau initial passé en paramètre "leTab", cette méthode renvoie un nouveau tableau "tabFreq" d'entiers où chaque case contient la fréquence d'apparition des valeurs dans le tableau initial.
     * Pour simplifier, on suppose que le tableau initial ne contient que des entiers compris entre 0 et max (>0).
     * Dès lors le tableau "tabFreq" se compose de (max+1) cases et chaque case "i" (0<=i<=max) contient le nombre de fois que l'entier "i" apparait dans le tableau initial.
     * On suppose que le tableau passé en paramètre est créé et possède au moins une valeur (nbElem > 0).
     * Ceci ne doit donc pas être vérifié.
     * Par contre, on vérifiera que le min est >= 0.
     * Dans le cas contraire, renvoyer un tableau "null".
     * @param leTab - le tableau initial
     * @param nbElem - le nombre d'entiers présents dans le tableau
     * @return le tableau des fréquences de taille (max+1) ou null si la méthode ne s'applique pas
     */
    int[] creerTabFreq(int[] leTab, int nbElem){ // f(n) = 12+10n
        int max = monSpleTab.leMax(leTab, nbElem); // f(n) = 5n+4 +1
        int[] tabFreq; // 1
        //Vérif du minimum
        boolean min=true;
        for(int i =0; i<nbElem && min; i++){
            if (leTab[i] < 0){
                min = false;
            }
        }
        //Calcul du tabFreq
        if(min){
            tabFreq = new int[max+1]; // 2
            for(int i=0; i<nbElem; i++){ // 2 / n+1 / 2n
                tabFreq[leTab[i]]++; // 2
            }
        }else {
            System.out.println("creerTabFreq() : Valeurs incompatibles");
            tabFreq = null;
        }
        return tabFreq;
    }

    /**
     * test de creerTabFreq()
     */
    void testCreerTabFreq(){
        System.out.println("\n*** Test de creerTabFreq()");
        System.out.println("** Cas normaux");
        testCasCreerTabFreq(new int[] {0,1,2,3,4,5,6,7,8,9},10, new int[] {1,1,1,1,1,1,1,1,1,1});
        testCasCreerTabFreq(new int[] {7,7,7,7,7,7,7},7, new int[] {0,0,0,0,0,0,0,7});
        testCasCreerTabFreq(new int[] {3,2,1,7,9,8,5,1,3,5,1,8,6,9},14, new int[] {0,3,1,2,0,2,1,1,2,2});

        System.out.println("** Cas limites");
        testCasCreerTabFreq(new int[] {10},1, new int[] {0,0,0,0,0,0,0,0,0,0,1});
        testCasCreerTabFreq(new int[] {0},1, new int[] {1});

        System.out.println("** Cas d'erreurs");
        testCasCreerTabFreq(new int[] {-2,0,5,7,1,-1},6, null);
    }

    /**
     * test d'un ca d'appel de creerTabFreq()
     * @param leTab - le tableau des valeurs
     * @param nbElem - indice Right de fin de tableau
     * @param result - le resultat attendu
     */
    void testCasCreerTabFreq(int[] leTab, int nbElem, int[] result){
        // Affichage
        System.out.print ("triRapide (");
        monSpleTab.afficherTab(leTab,leTab.length);
        System.out.print (", "+nbElem+") \t= ");
        int[] freq = creerTabFreq(leTab, nbElem);
        boolean ok = false;
        if(freq!=null){
            monSpleTab.afficherTab(result,result.length);
            ok = monSpleTab.egalite(result, freq, result.length, freq.length);
        } else {
            System.out.print("null");
        }
        System.out.print("\t : ");
        // Verification
        if (ok||freq==result){
            System.out.println ("OK");
        } else {
            System.err.println ("ERREUR");
        }  
    }



    /**
     * Tri par ordre croissant d'un tableau selon la méthode du tri par comptage de fréquences.
     * On suppose que le tableau passé en paramètre est créé et possède au moins une valeur (nbElem > 0).
     * Ceci ne doit donc pas être vérifié.
     * @param leTab - le tableau à trier par ordre croissant
     * @param nbElem - le nombre d'entiers que contient le tableau
     */
    void triParComptageFreq(int[] leTab, int nbElem){ // f(n) = 19+6max+16n
        int[] tabFreq = creerTabFreq(leTab, nbElem); // f(n) = 12+10n
        boolean ok = tabFreq != null;
        int total=0; // 2
        if(ok){
            for(int i=0; i<tabFreq.length; i++){ // 2 / 2*(max+1) / 2max
                for(int j = 0; j<tabFreq[i];j++){ // 2 /  / n+1 et 2n (indépendament de la boucle superieur)
                    leTab[total] = i; // 1
                    total++; // 2
                    cpt++;
                }
                cpt++;
            }
        }
    }

    /**
     * test de triParComptageFreq()
     */
    void testTriParComptageFreq(){
        System.out.println("\n*** Test de triParComptageFreq()");
        System.out.println("** Cas normaux");
        testCasTriParComptageFreq(new int[] {0,1,2,3,4,5,2,7,6},6);
        testCasTriParComptageFreq(new int[] {2,35,1,68,8,64,1,3,21,8},10);

        System.out.println("** Cas limites");
        testCasTriParComptageFreq(new int[5],5);
        testCasTriParComptageFreq(new int[] {8},1);

        System.out.println("** Cas d'erreur");
        testCasTriParComptageFreq(new int[] {-1},1);
    }

    /**
     * Test un cas d'appel de triParComptageFreq()
     * @param leTab - le tableau des valeurs
     * @param nbElem - indice Right de fin de tableau
     * @param result - le resultat attendu
     */
    void testCasTriParComptageFreq(int[] leTab, int nbElem){
        // Affichage
        System.out.print ("triParComptageFreq (");
        monSpleTab.afficherTab(leTab,leTab.length);
        System.out.print (", "+nbElem+") \t= ");
        // Appel
        triParComptageFreq(leTab, nbElem);
        boolean trie = verifTri(leTab, nbElem);
        int[] tabFreq = creerTabFreq(leTab, nbElem);

        monSpleTab.afficherTab(leTab,nbElem);
        System.out.print("\t : ");
        // Verification
        if (trie||tabFreq==null){
            System.out.println ("OK");
        } else {
            System.err.println ("ERREUR");
        }  
    }

    /**
     * Test de l'efficacité de triParComptageFreq()
     */
    void testTriParComptageFreqEfficacite(){ //Ɵ(max(n)+n)
        System.out.println("** Test de l'éfficacité");
        for (int i=8000000; i<=1024000000; i*=2){
            cpt = 0;
            int[] tab = new int[i];
            monSpleTab.remplirAleatoire(tab, i, 0, 100);
            int max =monSpleTab.leMax(tab, i);
            long debut = System.currentTimeMillis();
            triParComptageFreq(tab, i);
            long fin = System.currentTimeMillis();
            long temps=fin-debut;
            double cst=cpt/(double)(max+i+1);
            System.out.println("n="+i+"\t\tmax="+max+"\t\ttemps="+temps+"\t\tcompteur="+cpt+"\t\tconstante5="+cst);
        }
    }

    


    /**
     * Tri par ordre croissant d'un tableau selon la méthode du tri à bulles : tant que le tableau qu'il reste à trier a au moins 2 cases, permuter le contenu de 2 cases successives si leTab[i] > leTab[i+1].
     * On suppose que le tableau passé en paramètre est créé et possède au moins une valeur (nbElem > 0).
     * Ceci ne doit donc pas être vérifié.
     * @param leTab - le tableau à trier par ordre croissant
     * @param nbElem - le nombre d'entiers que contient le tableau
     */
    void triABulles(int[] leTab, int nbElem){ // dans le pire des cas : f(n)=3+5n+(3(n²-n+2)+9(n²-n))/2 = (12n²-2n+12)/2
        for(int i=0; i<nbElem; i++){ // 2 / n+1 / 2n
            for (int j=0; j<nbElem-i-1; j++){ // 2 / 3 / 2 | nbr de tour de boucle totale = Somme de n-1 à 1 = n*(n-1)/2 tours
                if (leTab[j]>leTab[j+1]){// 2
                    monSpleTab.echange(leTab, nbElem, j, j+1); // 5
                }
                cpt++;
            }
        }
    }

    /**
     * Test de TriABulles()
     */
    void testTriABulles(){
        System.out.println("\n*** Test de triABulles()");
        System.out.println("** Cas normaux");
        testCasTriRapide(new int[] {0,1,2,3,4,5,2,7,6},6);
        testCasTriRapide(new int[] {-2,35,1,68,8,64,1,3,21,8},10);

        System.out.println("** Cas limites");
        testCasTriRapide(new int[5],5);
        testCasTriRapide(new int[] {-8},1);
    }

    /**
     * Test d'un cas d'appel de a fonction triABulles()
     * @param leTab - le tableau des valeurs
     * @param nbElem - indice Right de fin de tableau
     * @param result - le resultat attendu
     */
    void testCasTriABulles(int[] leTab, int nbElem){
        // Affichage
        System.out.print ("triRapide (");
        monSpleTab.afficherTab(leTab,leTab.length);
        System.out.print (", "+nbElem+") \t= ");
        // Appel
        triABulles(leTab, nbElem);
        boolean trie = verifTri(leTab, nbElem);

        monSpleTab.afficherTab(leTab,nbElem);
        System.out.print("\t : ");
        // Verification
        if (trie == true){
            System.out.println ("OK");
        } else {
            System.err.println ("ERREUR");
        } 
    }

    /**
     * Test efficacité de triABulles()
     */
    void testTriABullesEfficacite(){ //Ɵ(n²)
        System.out.println("** Test de l'éfficacité");
        //calcul
        for (int i=4000; i<=128000; i*=2){
            cpt = 0;
            int[] tab = new int[i];
            for(int j =0; j<tab.length; j++){
                tab[j]=i-j;
            }
            long debut = System.currentTimeMillis();
            triABulles(tab, i);
            long fin = System.currentTimeMillis();
            long temps=fin-debut;
            //double cst = cpt/(i*(i+1)/(double)2);
            double cst = cpt/((double)i*i);
            System.out.println("n="+i+"\t\ttemps="+temps+"\t\tcompteur="+cpt+"\t\tconstante6="+cst);
        }
    }
}