/* Test d'algorithmes de tri :                    */
/*  - Tri par insertion                           */
/*  - Tri par selection                           */
/*  - Tri a bulle                                 */
/*  - Tri a bulle optimise                        */
/*  - Tri par fusion                              */
/*  - Tri rapide                                  */

import java.util.Date;
import java.util.Random;

public class TestTriGlobal {

/* Fonction d'affichage des valeurs contenues     */
/* dans un tableau de int                         */
  
  static void affichageTableau(int [] t) {
    for ( int i = 0 ; i < t.length ; i++ ) {
      Ecran.afficher(t[i]," "); }
    Ecran.sautDeLigne();
  }

/* Fonction de creation d'un tableau de 10 int    */
/* initialise avec des valeurs croissantes        */
  
  static int [] initRandCroissant(int n,long seed) {
    Random r = new Random(seed);
    int [] t = new int[n];
    t[0] =(int) (r.nextDouble()*10.0);
    for ( int i = 1 ; i < t.length ; i++ ) {
      t[i] = t[i-1] + (int) (r.nextDouble()*10.0); }
    return t;
  }

/* Fonction de creation d'un tableau de 10 int    */
/* initialise avec des valeurs croissantes        */
  
  static int [] initRandQuasiCroissantPC(int n,int nb,long seed) {
    Random r = new Random(seed);
    int [] t = initRandCroissant(n,seed);
    int i1;
    int i2;
    int aux;
    if ( nb != 0 )
      for ( int i = 0 ; i < nb ; i++ ) {
        i1 =(int) (r.nextDouble()*(n));
        i2 =(int) (r.nextDouble()*(n));
        aux = t[i1];
        t[i1] = t[i2];
        t[i2] = aux; }
    return t;
  }

/* Fonction de creation d'un tableau de 10 int    */
/* initialise avec des valeurs croissantes        */
  
  static int [] initRandQuasiCroissantPV(int n,int nb,long seed) {
    Random r = new Random(seed);
    int [] t = initRandCroissant(n,seed);
    int i1;
    int i2;
    int aux;
    if ( nb != 0 )
      for ( int i = 0 ; i < nb ; i++ ) {
        i1 =(int) (r.nextDouble()*(n-1));
        i2 = i1+1+(int) (r.nextDouble()*(t.length/50));
        if ( i2 < t.length ) {
          aux = t[i1];
          t[i1] = t[i2];
          t[i2] = aux; } }
    return t;
  }

/* Fonction de creation d'un tableau d'entiers    */
/* initialise avec des valeurs tirees au sort     */
/* entre 0 et 1000 inclus                         */
  
  static int [] initRand(int n,long seed) {
    Random r = new Random(seed);
    int [] t = new int[n];
    for ( int i = 0 ; i < t.length ; i++ ) {
      t[i] =(int) (r.nextDouble()*1000000001.0); }
    return t;
  }

/* Fonction de recherche de la position           */
/* d'un entier v dans un tableau d'entiers        */
/* restreint aux indices 0 a i                    */

  static int positionInsertion(int v,int l,int [] t) {
    int p = l+1;
    while ( ( p-1 >= 0 ) && ( v < t[p-1] ) ) {
      p--; }
    return p;
  }

/* Fonction de decalage de une cellule            */
/* vers la droite du contenu des cellules         */
/* de l'indice indi a l'indice indf               */
/* d'un tableau d'entiers                         */

  static void decalage(int indi,int indf,int [] t) {
    for ( int i = indf ; i >= indi ; i-- ) {
      t[i] = t[i-1]; }
  }

/* Fonction de tri par insertion d'un tableau     */
/* d'entiers                                      */

  static void triInsertion(int [] t) {
    int p;
    int v;
    for ( int i = 1 ; i < t.length ; i++ ) {
      v = t[i];
      p = positionInsertion(v,i-1,t);
      if ( p != i ) {
        decalage(p+1,i,t);
        t[p] = v; } }
  }

/* Fonction de tri a bulle d'un tableau d'entiers */

  static void triBulle(int [] t) {
    int aux;
    int ne = t.length-1;
    int np = t.length-1;
    for ( int i = 0 ; i < ne ; i++ ) {
      for ( int j = 0 ; j < np ; j++ ) {
        if ( t[j] > t[j+1] ) {
          aux = t[j];
          t[j] = t[j+1];
          t[j+1] = aux; } }
      np--; }
  }

/* Fonction de tri a bulle optimise               */
/* d'un tableau d'entiers                         */

  static void triBulleOptimise(int [] t) {
    int aux;
    boolean permutation;
    int np = t.length-1;
    do {
      permutation = false;
      for ( int j = 0 ; j < np ; j++ ) {
        if ( t[j] > t[j+1] ) {
          aux = t[j];
          t[j] = t[j+1];
          t[j+1] = aux;
          permutation = true; } }
      np--; }
    while ( permutation );
  }

/* Fonction de recherche de l'indice de la valeur */
/* maximale d'un tableau restreint                */
/* a ses n premieres valeurs                      */
  
  static int indiceMaximum(int n,int [] t) {
    int max = t[n];
    int iMax = n;
    for ( int i = n-1 ; i >= 0 ; i-- ) {
      if ( t[i] > max ) {
        max = t[i];
        iMax = i; } }
    return iMax;
  }

/* Fonction de tri par selection                  */
/* d'un tableau d'entiers                         */

  static void triSelection(int [] t) {
    int aux;
    int ne = t.length-1;
    int np = t.length-1;
    int iMax;
    for ( int i = 0 ; i < ne ; i++ ) {
      iMax = indiceMaximum(np,t);
      if ( iMax != np ) {
        aux = t[iMax];
        t[iMax] = t[np];
        t[np] = aux; }
      np--; }
  }

/* Fonction de tri par fusion                     */
/* d'un tableau d'entiers                         */

  static void fusion(int [] t,int i1,int t1,int i2,int t2) {
    int deb = i1;
    int l = t1+t2;
    int l1 = i1+t1;
    int l2 = i2+t2;
    int [] tf = new int[l];
    for ( int i = 0 ; i < l ; i++ ) {
      if ( i1 == l1 ) {
        tf[i] = t[i2];
        i2++; }
        else {
        if ( i2 == l2 ) {
          tf[i] = t[i1];
          i1++; }
          else {
          if ( t[i1] < t[i2] ) {
            tf[i] = t[i1];
            i1++; }
            else {
            tf[i] = t[i2];
            i2++; } } } }
    for ( int i = 0 ; i < l ; i++ ) {
      t[deb+i] = tf[i]; }
  }
  
  static void triFusion(int [] t,int indi,int indf) {
    int iMedian;
    int aux;
    switch ( indf-indi ) {
      case 0 :
        break;
      case 1 : {
        if ( t[indf] < t[indi] ) {
          aux = t[indi];
          t[indi] = t[indf];
          t[indf] = aux; } }
        break;
      default : {
        iMedian =(indi+indf)/2;
        triFusion(t,indi,iMedian);
        triFusion(t,iMedian+1,indf);
        fusion(t,indi,iMedian-indi+1,iMedian+1,indf-iMedian); } }
  }
  
  static void triFusion(int [] t) {
    triFusion(t,0,t.length-1);
  }

/* Fonction de recherche vers la droite           */
/* de la prochaine valeur superieure au pivot     */
/* Recherche de l'indice i jusqu'a l'indice max   */

  static int nextSuperieurPivot(int i,int [] t,
                                int max,int pivot) {
    while ( ( i <= max ) && ( t[i] <= pivot ) ) {
      i++; }
    return i;
  }

/* Fonction de recherche vers la gauche           */
/* de la prochaine valeur inferieure au pivot     */
/* Recherche de l'indice i jusqu'a l'indice min   */
  
  static int nextInferieurPivot(int i,int [] t,
                                int min,int pivot) {
    while ( ( i >= min ) && ( t[i] > pivot ) ) {
      i--; }
    return i;
  }

/* Fonction de reorganisation d'un tableau        */
/* d'entiers des indices indi a indf compris      */
/* Placement en partie gauche de toutes           */
/* les valeurs inferieures au pivot,              */
/* et en partie droite des valeurs superieures    */
/* Retour de la position du pivot                 */
  
  static int reorganisation(int [] t,int pivot,
                            int indi,int indf) {
    int iinf;
    int isup;
    int aux;
    iinf = nextSuperieurPivot(indi,t,indf,pivot);
    isup = nextInferieurPivot(indf,t,indi,pivot);
    while ( iinf < isup ) {
      aux = t[iinf];
      t[iinf] = t[isup];
      t[isup] = aux;
      iinf = nextSuperieurPivot(iinf,t,isup,pivot);
      isup = nextInferieurPivot(isup,t,iinf,pivot); }
    return iinf;
  }
  
/* Fonction de tri par QuickSort d'un tableau     */
/* d'entiers des indices indi a indf compris      */
/* Pivot choisi a la valeur moyenne des valeurs   */
/* min et max                                     */

  static void triRapide(int [] t,int indi,int indf,
                        int min,int max) {
    int iMedian;
    int aux;
    int pivot;
    if ( indf-indi == 1 ) {
      if ( t[indf] < t[indi] ) {
        aux = t[indi];
        t[indi] = t[indf];
        t[indf] = aux; } }
      else {
      pivot = (min+max)>>1;
      iMedian = reorganisation(t,pivot,indi,indf);
      if ( ( iMedian != indi ) && ( iMedian < indf ) ) {
        triRapide(t,indi,iMedian,min,pivot);
        triRapide(t,iMedian+1,indf,pivot+1,max); } }
  }

/* Fonction de tri par QuickSort                  */
/* de l'ensemble d'un tableau d'entiers           */
/* Pivot choisi a la valeur moyenne des valeurs   */
/* min et max du tableau                          */

  static void triRapide(int [] t) {
    int min = t[0];
    int max = t[0];
    for ( int i = 1 ; i < t.length ; i++ ) {
      if ( t[i] < min ) {
        min = t[i]; }
      if ( t[i] > max ) {
        max = t[i]; } }
    triRapide(t,0,t.length-1,min,max);
  }

/* Programme principal                            */

  public static void main(String [] args) {
    int [] t;
    int taille;
    int nb;
    Ecran.afficher("SVP, nombre de tests   : ");
    nb = Clavier.saisirInt();
    Ecran.afficherln("Tableau quelconque");
    for ( taille = 2 ; taille <= 100000000 ; taille = next(taille) ) {
      { { long dt;
          { Date ddi = new Date();
            for ( int i = 0 ; i < nb ; i++ ) {
//              t = initRand(taille,i+1);
//              t = initRandCroissant(taille,i+1);
              t = initRandQuasiCroissantPC(taille,taille/10,i+1);
//              t = initRandQuasiCroissantPV(taille,taille/2,i+1);
              /*System.gc(); */ }
            Date ddf = new Date();
            dt = ddf.getTime()-ddi.getTime(); }
          { Date ddi = new Date();
            for ( int i = 0 ; i < nb ; i++ ) {
//              t = initRand(taille,i+1);
//              t = initRandCroissant(taille,i+1);
              t = initRandQuasiCroissantPC(taille,taille/10,i+1);
//              t = initRandQuasiCroissantPV(taille,taille/2,i+1);
              triFusion(t);
              /*System.gc(); */ }
            Date ddf = new Date();
            Ecran.afficher("Tri fusion & rapide : ",
                             nb," ",
                             taille," ",
                             dt," ",
                             //(ddf.getTime()-ddi.getTime()-dt)," ",
                             (double) ((ddf.getTime()-ddi.getTime())-dt)/nb," "); }
          //~ { Date ddi = new Date();
            //~ for ( int i = 0 ; i < nb ; i++ ) {
//~ //              t = initRand(taille,i+1);
//~ //              t = initRandCroissant(taille,i+1);
              //~ t = initRandQuasiCroissantPC(taille,taille/10,i+1);
//~ //              t = initRandQuasiCroissantPV(taille,taille/2,i+1);
              //~ triBulle(t);
              //~ /*System.gc(); */ }
            //~ Date ddf = new Date();
            //~ Ecran.afficher(//(ddf.getTime()-ddi.getTime()-dt)," ",
                             //~ (double) ((ddf.getTime()-ddi.getTime())-dt)/nb," "); }
          { Date ddi = new Date();
            for ( int i = 0 ; i < nb ; i++ ) {
//              t = initRand(taille,i+1);
//              t = initRandCroissant(taille,i+1);
              t = initRandQuasiCroissantPC(taille,taille/10,i+1);
//              t = initRandQuasiCroissantPV(taille,taille/2,i+1);
              triRapide(t);
              /*System.gc(); */ }
            Date ddf = new Date();
            Ecran.afficherln(//(ddf.getTime()-ddi.getTime()-dt)," ",
                             (double) ((ddf.getTime()-ddi.getTime())-dt)/nb," "); } } } }
  }
  
  static int next(int n) {
    switch (n) {
      case 1         : return(2);
      case 2         : return(5);
      case 5         : return(10);
      case 10        : return(12);
      case 12        : return(15);
      case 15        : return(20);
      case 20        : return(30);
      case 30        : return(50);
      case 50        : return(70);
      case 70        : return(100);
      case 100       : return(120);
      case 120       : return(150);
      case 150       : return(200);
      case 200       : return(300);
      case 300       : return(500);
      case 500       : return(700);
      case 700       : return(1000);
      case 1000      : return(1200);
      case 1200      : return(1500);
      case 1500      : return(2000);
      case 2000      : return(3000);
      case 3000      : return(5000);
      case 5000      : return(7000);
      case 7000      : return(10000);
      case 10000     : return(12000);
      case 12000     : return(15000);
      case 15000     : return(20000);
      case 20000     : return(30000);
      case 30000     : return(50000);
      case 50000     : return(70000);
      case 70000     : return(100000);
      case 100000    : return(120000);
      case 120000    : return(150000);
      case 150000    : return(200000);
      case 200000    : return(300000);
      case 300000    : return(500000);
      case 500000    : return(700000);
      case 700000    : return(1000000);
      case 1000000   : return(1200000);
      case 1200000   : return(1500000);
      case 1500000   : return(2000000);
      case 2000000   : return(3000000);
      case 3000000   : return(5000000);
      case 5000000   : return(7000000);
      case 7000000   : return(10000000);
      case 10000000  : return(12000000);
      case 12000000  : return(15000000);
      case 15000000  : return(20000000);
      case 20000000  : return(30000000);
      case 30000000  : return(50000000);
      case 50000000  : return(70000000);
      case 70000000  : return(100000000);
      case 100000000 : return(120000000);
      case 120000000 : return(150000000);
      case 150000000 : return(200000000);
      case 200000000 : return(300000000);
      case 300000000 : return(500000000);
      case 500000000 : return(700000000);
      case 700000000 : return(1000000000);
        }
    return(1000000000);
  }
}