import java.util.Random;

// java cheatsheet : http://introcs.cs.princeton.edu/java/11cheatsheet/
// cheatsheet from C to java ?
// sur visualgo la partition du quicksort est la méthode Lomuto

public class Sortingetudiant
{
    public static int nbAffectations;
    public static int nbComparaisons;
    public static long debut;
    public static long fin;
    public static long tempsExecution;
    
    
    public static void identite(int[] tab)
    {
        for (int i=0;i<tab.length;i++)
            tab[i]=i;
    }
    
    public static void identiteInverse(int[] tab)
    {
        int N=tab.length;
        for (int i=0;i<N;i++)
            tab[i]=N-1-i;
    }
    
    public static void tableauAleatoire(int[] tab,int borne)
    {
        int N=tab.length;
        Random generator = new Random(42);
        for (int i=0;i<N;i++)
            tab[i]=generator.nextInt(borne);
    }
    
    public static void afficher(int[] tab)
    {
        System.out.print("[");
        for (int i=0;i<tab.length;i++)
            System.out.print(tab[i]+" ");
        System.out.print("]");
    }
    
    public static void estTrie(int[] tab)
    {
        for (int i=0;i<tab.length-1;i++)
            if (tab[i]>tab[i+1])
        { System.out.println("Le tableau n'est pas trié");
            return;}
        System.out.println("Le tableau est trié.");
    }
    
    public static void selection(int[] tab)
    {
        nbAffectations=0;
        nbComparaisons=0;
        int N=tab.length;
        
        // TO DO
    }
    
    
    
    public static void insertion(int[] tab)
    {
        nbAffectations=0;
        nbComparaisons=0;
        int N=tab.length;
        
        // TO DO
    }
    
    
    
    public static void fusion(int[] tab)
    {
        fusion(tab,0,tab.length);
    }
    
    public static void fusion(int[] tab,int debut,int fin)
    {
        nbAffectations=0;
        nbComparaisons=0;
    
        // TO DO
    }
    
    
    
    // quicksort
    
    public static void quicksort(int[] tab)
    {
        quicksort(tab,0,tab.length-1);
    }
    
    public static void quicksort(int[] tab,int debut,int fin)
    {
        if (fin<=debut) return;
        int k=partition(tab,debut,fin);
        quicksort(tab,debut,k-1);
        quicksort(tab,k+1,fin);
    }
    
    public static int partition(int[] tab,int debut,int fin)
    {
        // TO DO
    }
    
    
        
    public static void main(String[] args)
    {
        int TAILLE=10; 
        int[] tab = new int[TAILLE];
        
        // identite(tab);
        // identiteInverse(tab);
        // tableauAleatoire(tab,1000*1000*1000);
        // afficher(tab);
        
                
        
        /*
         * test selection
         */
        
        
        System.out.println(">>> Tri selection ");
        
        // vide
        int[] tab0_selection = {};
        afficher(tab0_selection);
        selection(tab0_selection);
        System.out.print(" -> selection -> ");
        afficher(tab0_selection);
        System.out.println();
        
        // une case
        int[] tab1_selection = {1};
        afficher(tab1_selection);
        selection(tab1_selection);
        System.out.print(" -> selection -> ");
        afficher(tab1_selection);
        System.out.println();
        
        // 5 cases triées
        int[] tab5_1_selection = {1,2,3,4,5};
        afficher(tab5_1_selection);
        selection(tab5_1_selection);
        System.out.print(" -> selection -> ");
        afficher(tab5_1_selection);
        System.out.println();
        
        // 5 cases "aléatoires"
        int[] tab5_selection = {2,4,5,3,1};
        afficher(tab5_selection);
        selection(tab5_selection);
        System.out.print(" -> selection -> ");
        afficher(tab5_selection);
        System.out.println();
        
        
        /*
         * test insertion
         */
        
        
        System.out.println(">>> Tri insertion ");
        
        // vide
        int[] tab0_insertion = {};
        afficher(tab0_insertion);
        insertion(tab0_insertion);
        System.out.print(" -> insertion -> ");
        afficher(tab0_insertion);
        System.out.println();
        
        // une case
        int[] tab1_insertion = {1};
        afficher(tab1_insertion);
        insertion(tab1_insertion);
        System.out.print(" -> insertion -> ");
        afficher(tab1_insertion);
        System.out.println();
        
        // 5 cases triées
        int[] tab5_1_insertion = {1,2,3,4,5};
        afficher(tab5_1_insertion);
        insertion(tab5_1_insertion);
        System.out.print(" -> insertion -> ");
        afficher(tab5_1_insertion);
        System.out.println();
        
        // 5 cases "aléatoires"
        int[] tab5_insertion = {2,4,5,3,1};
        afficher(tab5_insertion);
        insertion(tab5_insertion);
        System.out.print(" -> insertion -> ");
        afficher(tab5_insertion);
        System.out.println();
        
        
        /*
         * test quicksort
         */
        
        System.out.println(">>> Tri quicksort ");
        
        // vide
        int[] tab0_quicksort = {};
        afficher(tab0_quicksort);
        quicksort(tab0_quicksort);
        System.out.print(" -> quicksort -> ");
        afficher(tab0_quicksort);
        System.out.println();
        
        // une case
        int[] tab1_quicksort = {1};
        afficher(tab1_quicksort);
        quicksort(tab1_quicksort);
        System.out.print(" -> quicksort -> ");
        afficher(tab1_quicksort);
        System.out.println();
        
        // 5 cases triées
        int[] tab5_1_quicksort = {1,2,3,4,5};
        afficher(tab5_1_quicksort);
        quicksort(tab5_1_quicksort);
        System.out.print(" -> quicksort -> ");
        afficher(tab5_1_quicksort);
        System.out.println();
        
        // 5 cases "aléatoires"
        int[] tab5_quicksort = {2,4,5,3,1};
        afficher(tab5_quicksort);
        quicksort(tab5_quicksort);
        System.out.print(" -> quicksort -> ");
        afficher(tab5_quicksort);
        System.out.println();
        
        /*
         * test fusion
         */
        
        // vide
        int[] tab0_fusion = {};
        afficher(tab0_fusion);
        fusion(tab0_fusion);
        System.out.print(" -> fusion -> ");
        afficher(tab0_fusion);
        System.out.println();
        
        // une case
        int[] tab1_fusion = {1};
        afficher(tab1_fusion);
        fusion(tab1_fusion);
        System.out.print(" -> fusion -> ");
        afficher(tab1_fusion);
        System.out.println();
        
        // 5 cases triées
        int[] tab5_1_fusion = {1,2,3,4,5};
        afficher(tab5_1_fusion);
        fusion(tab5_1_fusion);
        System.out.print(" -> fusion -> ");
        afficher(tab5_1_fusion);
        System.out.println();
        
        // 5 cases "aléatoires"
        int[] tab5_fusion = {2,4,5,3,1};
        afficher(tab5_fusion);
        fusion(tab5_fusion);
        System.out.print(" -> fusion -> ");
        afficher(tab5_fusion);
        System.out.println();
                
        /*
        try {
            for (int i=0;i<10;i++)
            {
                tableauAleatoire(tab,1000*1000*1000);
                debut=System.currentTimeMillis();
                // quicksort(tab);
                //java.util.Arrays.sort(tab);
                fusion(tab);
                fin=System.currentTimeMillis();
                tempsExecution=fin-debut;
                
                // afficher(tab);
                // System.out.print(nbAffectations+" affectations  ");
                // System.out.print(nbComparaisons+" comparaisons  ");
                System.out.print(tempsExecution+" ms");
                System.out.println();
            }
        } catch(java.lang.OutOfMemoryError e) {
            System.out.println("Plus d'espace mémoire pour " + TAILLE + " entiers");   
        }
        */
        
    }
}