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

/* 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 [] initRandQuasiCroissant(int n,long seed) {
    Random r = new Random(seed);
    int [] t = initRandCroissant(n,seed);
    int nb = 10;
    int i1;
    int i2;
    int aux;
    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 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()*1001.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 indgi;
    int indgf;
    int inddi;
    int inddf;
    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;
        indgi = indi;
        indgf = iMedian;
        inddi = iMedian+1;
        inddf = indf;
        triFusion(t,indgi,indgf);
        triFusion(t,inddi,inddf);
        fusion(t,indgi,indgf-indgi+1,inddi,inddf-inddi+1); } }
  }
  
  static void triFusion(int [] t) {
    triFusion(t,0,t.length-1);
  }

/* Programme principal                            */

  public static void main(String [] args) {
    int [] t;
    int taille;
    int nb;
    Ecran.afficher("SVP, taille du tableau : ");
    taille = Clavier.saisirInt();
    Ecran.afficher("SVP, nombre de tests   : ");
    nb = Clavier.saisirInt();
    { Ecran.afficherln("Tableau quelconque");
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRand(taille,i+1);
            triInsertion(t); }
          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); }
          Date ddf = new Date();
          Ecran.afficherln("Tri insertion    : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } }
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRand(taille,i+1);
            triBulle(t); }
          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); }
          Date ddf = new Date();
          Ecran.afficherln("Tri a bulle      : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } }
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRand(taille,i+1);
            triBulleOptimise(t); }
          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); }
          Date ddf = new Date();
          Ecran.afficherln("Tri a bulle opt. : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } }
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRand(taille,i+1);
            triSelection(t); }
          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); }
          Date ddf = new Date();
          Ecran.afficherln("Tri selection    : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } }
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRand(taille,i+1);
            triFusion(t); }
          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); }
          Date ddf = new Date();
          Ecran.afficherln("Tri fusion       : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } } }
    { Ecran.afficherln("Tableau trie");
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandCroissant(taille,i+1);
            triInsertion(t); }
          Date ddf = new Date();
          dt = ddf.getTime()-ddi.getTime(); }
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandCroissant(taille,i+1); }
          Date ddf = new Date();
          Ecran.afficherln("Tri insertion    : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } }
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandCroissant(taille,i+1);
            triBulle(t); }
          Date ddf = new Date();
          dt = ddf.getTime()-ddi.getTime(); }
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandCroissant(taille,i+1); }
          Date ddf = new Date();
          Ecran.afficherln("Tri a bulle      : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } }
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandCroissant(taille,i+1);
            triBulleOptimise(t); }
          Date ddf = new Date();
          dt = ddf.getTime()-ddi.getTime(); }
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandCroissant(taille,i+1); }
          Date ddf = new Date();
          Ecran.afficherln("Tri a bulle opt. : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } }
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandCroissant(taille,i+1);
            triSelection(t); }
          Date ddf = new Date();
          dt = ddf.getTime()-ddi.getTime(); }
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandCroissant(taille,i+1); }
          Date ddf = new Date();
          Ecran.afficherln("Tri selection    : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } }
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandCroissant(taille,i+1);
            triFusion(t); }
          Date ddf = new Date();
          dt = ddf.getTime()-ddi.getTime(); }
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandCroissant(taille,i+1); }
          Date ddf = new Date();
          Ecran.afficherln("Tri fusion       : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } } }
    { Ecran.afficherln("Tableau quasi-trie");
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandQuasiCroissant(taille,i+1);
            triInsertion(t); }
          Date ddf = new Date();
          dt = ddf.getTime()-ddi.getTime(); }
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandQuasiCroissant(taille,i+1); }
          Date ddf = new Date();
          Ecran.afficherln("Tri insertion    : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } }
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandQuasiCroissant(taille,i+1);
            triBulle(t); }
          Date ddf = new Date();
          dt = ddf.getTime()-ddi.getTime(); }
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandQuasiCroissant(taille,i+1); }
          Date ddf = new Date();
          Ecran.afficherln("Tri a bulle      : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } }
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandQuasiCroissant(taille,i+1);
            triBulleOptimise(t); }
          Date ddf = new Date();
          dt = ddf.getTime()-ddi.getTime(); }
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandQuasiCroissant(taille,i+1); }
          Date ddf = new Date();
          Ecran.afficherln("Tri a bulle opt. : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } }
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandQuasiCroissant(taille,i+1);
            triSelection(t); }
          Date ddf = new Date();
          dt = ddf.getTime()-ddi.getTime(); }
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandQuasiCroissant(taille,i+1); }
          Date ddf = new Date();
          Ecran.afficherln("Tri selection    : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } }
      { long dt;
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandQuasiCroissant(taille,i+1);
            triFusion(t); }
          Date ddf = new Date();
          dt = ddf.getTime()-ddi.getTime(); }
        { Date ddi = new Date();
          for ( int i = 0 ; i < nb ; i++ ) {
            t = initRandQuasiCroissant(taille,i+1); }
          Date ddf = new Date();
          Ecran.afficherln("Tri fusion       : ",
                           ddf.getTime()-ddi.getTime()," ",
                           dt," ",
                           dt-(ddf.getTime()-ddi.getTime())); } } }
  }
}