/* 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 Tri {

/* 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 iMin;
  static int iMax;
  
  static void indiceMinimumEtMaximum(int ni,int nf,int [] t) {
    int min;
    int max;
    min = max = t[ni];
    iMax = iMin = ni;
    for ( int i = ni+1 ; i <= nf ; i++ ) {
      if ( t[i] < min ) {
        min = t[i];
        iMin = i; }
      if ( t[i] > max ) {
        max = t[i];
        iMax = i; } }
  }

/* Fonction de tri par selection avec min-max     */
/* applique a un tableau d'entiers                */

  static void triSelectionOptimise(int [] t) {
    int aux;
    int ne = (t.length-1)>>1;
    int ni = 0;
    int nf = t.length-1;
    for ( int i = 0 ; i < ne ; i++ ) {
      indiceMinimumEtMaximum(ni,nf,t);
      if ( ( iMin != nf ) && ( iMax != ni ) ) {
        aux = t[nf];
        t[nf] = t[iMax];
        t[iMax] = aux;
        aux = t[ni];
        t[ni] = t[iMin];
        t[iMin] = aux; }
        else {
        if ( ( iMin == nf ) && ( iMax == ni ) ) {
          aux = t[ni];
          t[ni] = t[nf];
          t[nf] = aux; }
          else {
          if ( iMin == nf ) {
            aux = t[ni];
            t[ni] = t[nf];
            t[nf] = t[iMax];
            t[iMax] = aux; }
            else {
            aux = t[nf];
            t[nf] = t[ni];
            t[ni] = t[iMin];
            t[iMin] = aux; } } }
      ni++;
      nf--; }
    if ( t.length%2 == 0 ) {
      if ( t[ni] > t[nf] ) {
        aux = t[ni];
        t[ni] = t[nf];
        t[nf] = aux; }
    }
  }
 
/* Fonction de recherche de l'indice de la valeur */
/* maximale d'un tableau restreint                */
/* a ses n premieres valeurs                      */
  
  static int indiceDuMaximum(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 = indiceDuMaximum(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 int [] tf;
  
  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;
    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) {
    tf = new int[t.length];
    triFusion(t,0,t.length-1);
  }

  static int pivotage(int [] t,int indi,int indf,int pivot) {
    int aux;
    aux = t[pivot];
    t[pivot] = t[indf];
    t[indf] = aux;
    int j = indi;
    for ( int i = indi ; i < indf ; i++ ) {
      if ( t[i] <= t[indf] ) {
        aux = t[i];
        t[i] = t[j];
        t[j] = aux;
        j++; } }
    aux = t[indf];
    t[indf] = t[j];
    t[j] = aux;
    return j;
  }

/* 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 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 = (indi+indf)>>1;
      iMedian = pivotage(t,indi,indf,pivot);
      if ( iMedian > indi+1 ) {
        triRapide(t,indi,iMedian-1); }
      if ( iMedian < indf-1 ) {
        triRapide(t,iMedian+1,indf); } }
  }

/* 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) {
    triRapide(t,0,t.length-1);
  }

/* Fonction de tri naif                           */
/* applique a un tableau d'entiers                */

  static void triNaif(int [] t) {
    int [] tc = new int[t.length];
    int indice;
    int indf = t.length-1;
    int min;
    for ( int i = 0 ; i < t.length ; i++ )
      tc[i] = t[i];
    for ( int i = 0 ; i < t.length ; i++ ) {
      indice = indf;
      min = tc[indf];
      for ( int j = indf-1 ; j >= 0 ; j-- ) {
        if ( tc[j] < min ) {
          min = tc[j];
          indice = j; } }
      t[i] = tc[indice];
      tc[indice] = tc[indf];
      indf--; }
  }

/* 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 = initRandQuasiCroissantPC(taille,taille/10,i+1);
//              t = initRandQuasiCroissantPV(taille,taille/2,i+1);
//              t = initRandCroissant(taille,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 = initRandQuasiCroissantPC(taille,taille/10,i+1);
//              t = initRandQuasiCroissantPV(taille,taille/2,i+1);
//              t = initRandCroissant(taille,i+1);
              triNaif(t);
              /*System.gc(); */ }
            Date ddf = new Date();
            Ecran.afficher("Tri Sopt : ",
                             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 = initRandQuasiCroissantPC(taille,taille/10,i+1);
//~ //              t = initRandQuasiCroissantPV(taille,taille/2,i+1);
//~ //              t = initRandCroissant(taille,i+1);
              //~ triSelection(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 = initRandQuasiCroissantPC(taille,taille/10,i+1);
//~ //              t = initRandQuasiCroissantPV(taille,taille/2,i+1);
//~ //              t = initRandCroissant(taille,i+1);
              //~ triSelectionOptimise(t);
              //~ /*System.gc(); */ }
            //~ Date ddf = new Date();
            //~ Ecran.afficher(//(ddf.getTime()-ddi.getTime()-dt)," ",
                             //~ (double) ((ddf.getTime()-ddi.getTime())-dt)/nb," "); }
      Ecran.sautDeLigne();
    } } }
  }
  
  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);
  }
  
  static int next2(int n) {
    switch (n) {
      case 1         : return(2);
      case 2         : return(3);
      case 3         : return(4);
      case 4         : return(5);
      case 5         : return(6);
      case 6         : return(7);
      case 7         : return(8);
      case 8         : return(9);
      case 9         : return(10);
      case 10        : return(11);
      case 11        : return(12);
      case 12        : return(13);
      case 13        : return(14);
      case 14        : return(15);
      case 15        : return(16);
      case 16        : return(17);
      case 17        : return(18);
      case 18        : return(19);
      case 19        : return(20);
      case 20        : return(22);
      case 22        : return(24);
      case 24        : return(26);
      case 26        : return(28);
      case 28        : return(30);
      case 30        : return(35);
      case 35        : return(40);
      case 40        : return(45);
      case 45        : return(50);
      case 50        : return(55);
      case 55        : return(60);
      case 60        : return(65);
      case 65        : return(70);
      case 70        : return(75);
      case 75        : return(80);
      case 80        : return(85);
      case 85        : return(90);
      case 90        : return(95);
      case 95        : return(100);
      case 100       : return(110);
      case 110       : return(120);
      case 120       : return(130);
      case 130       : return(140);
      case 140       : return(150);
      case 150       : return(160);
      case 160       : return(170);
      case 170       : return(180);
      case 180       : return(190);
      case 190       : return(200);
      case 200       : return(220);
      case 220       : return(240);
      case 240       : return(260);
      case 260       : return(280);
      case 280       : return(300);
      case 300       : return(350);
      case 350       : return(400);
      case 400       : return(450);
      case 450       : return(500);
      case 500       : return(550);
      case 550       : return(600);
      case 600       : return(650);
      case 650       : return(700);
      case 700       : return(750);
      case 750       : return(800);
      case 800       : return(850);
      case 850       : return(900);
      case 900       : return(950);
      case 950       : return(1000);
      case 1000      : return(1100);
      case 1100      : return(1200);
      case 1200      : return(1300);
      case 1300      : return(1400);
      case 1400      : return(1500);
      case 1500      : return(1600);
      case 1600      : return(1700);
      case 1700      : return(1800);
      case 1800      : return(1900);
      case 1900      : return(2000);
      case 2000      : return(2200);
      case 2200      : return(2400);
      case 2400      : return(2600);
      case 2600      : return(2800);
      case 2800      : return(3000);
      case 3000      : return(3500);
      case 3500      : return(4000);
      case 4000      : return(4500);
      case 4500      : return(5000);
      case 5000      : return(5500);
      case 5500      : return(6000);
      case 6000      : return(6500);
      case 6500      : return(7000);
      case 7000      : return(7500);
      case 7500      : return(8000);
      case 8000      : return(8500);
      case 8500      : return(9000);
      case 9000      : return(9500);
      case 9500      : return(10000);
        }
    return(1000000000);
  }

/* Programme principal                            */

  public static void main2(String [] args) {
    /*{ int taille = 200;
      int [] t1 = initRand(taille,1);
      int [] t2 = initRandCroissant(taille,2);
      int [] t3 = initRandQuasiCroissantPC(taille,taille/10,3);
      int [] t4 = initRandQuasiCroissantPV(taille,taille/2,4);
      affichageTableau(t1);
      Ecran.sautDeLigne();
      affichageTableau(t2);
      Ecran.sautDeLigne();
      affichageTableau(t3);
      Ecran.sautDeLigne();
      affichageTableau(t4);
      Ecran.sautDeLigne(); } */
    int [] t;
    int taille;
    int nb;
    Ecran.afficher("SVP, nombre de tests   : ");
    nb = Clavier.saisirInt();
    Ecran.afficherln("Tableau quelconque");
    for ( taille = 70 ; taille <= 10000 ; 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);
              triInsertion(t);
              /*System.gc(); */ }
            Date ddf = new Date();
            Ecran.afficher("Tri I, S, B, BO, F & R : ",
                             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);
              triSelection(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);
              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);
              triBulleOptimise(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);
              triFusion(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," "); } } } }
  }
}