/* Recherche de la presence d'une valeur entiere */
/* dans un tableau d'entiers trie                */
/* par ordre croissant                           */
/* Methodes sequentielle et dichotomique         */

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

public class Tri2 {

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

/* Fonction de creation d'un tableau de 10 int    */
/* initialise avec des valeurs croissantes        */
  
  static void initRandQuasiCroissantPC(int n,int [] t,int nb,Random r) {
    initRandCroissant(n,t,r);
    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; }
  }

/* Fonction de creation d'un tableau de 10 int    */
/* initialise avec des valeurs croissantes        */
  
  static void initRandQuasiCroissantPV(int n,int [] t,int nb,Random r) {
    initRandCroissant(n,t,r);
    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;
        if ( i2 < n ) {
          aux = t[i1];
          t[i1] = t[i2];
          t[i2] = aux; } }
  }

/* Fonction de creation d'un tableau d'entiers    */
/* initialise avec des valeurs tirees au sort     */
/* entre 0 et 1000 inclus                         */
  
  static void initRand(int n,int [] t,Random r,double max) {
    for ( int i = 0 ; i < n ; i++ ) {
      t[i] =(int) (r.nextDouble()*max); }
  }
  
/* Fonction d'affichage des valeurs contenues    */
/* dans un tableau de int                        */
  
  static void affichageTableau(int n,int [] t) {
    for ( int i = 0 ; i < n ; i++ ) {
      Ecran.afficherln(t[i]," "); }
  }

/* 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 n,int [] t) {
    int p;
    int v;
    for ( int i = 1 ; i < n ; 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 n,int [] t) {
    int aux;
    int ne = n-1;
    int np = n-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 n,int [] t) {
    int aux;
    boolean permutation;
    int np = n-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 n,int [] t) {
    int aux;
    int ne = (n-1)>>1;
    int ni = 0;
    int nf = n-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 ( n%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 n,int [] t) {
    int aux;
    int ne = n-1;
    int np = n-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 n,int [] t) {
    tf = new int[n];
    triFusion(t,0,n-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 n,int [] t) {
    triRapide(t,0,n-1);
  }

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

  static void triNaif(int n,int [] t) {
    int [] tc = new int[n];
    int indice;
    int indf = n-1;
    int min;
    for ( int i = 0 ; i < n ; i++ )
      tc[i] = t[i];
    for ( int i = 0 ; i < n ; 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--; }
  }

  static void testsTri(int temps,int ni,int nf,int inc) {
    Ecran.formater("Ensembles triés\n");
    Ecran.formater("Bulle BulleOptimisé Sélection Sélection2 Insertion Fusion Rapide\n");
    Ecran.formater("%10s","Taille");
    Ecran.formater("%12s%14s%22s%14s",
                   "Appels","Temps total","Temps moyen",
                   "o(n*n)");
    Ecran.formater("%12s%14s%22s%14s",
                   "Appels","Temps total","Temps moyen",
                   "o(n*n)");
    Ecran.formater("%12s%14s%22s%14s",
                   "Appels","Temps total","Temps moyen",
                   "o(n*n)");
    Ecran.formater("%12s%14s%22s%14s",
                   "Appels","Temps total","Temps moyen",
                   "o(n*n)");
    Ecran.formater("%12s%14s%22s%14s",
                   "Appels","Temps total","Temps moyen",
                   "o(n*n)");
    Ecran.formater("%12s%14s%22s%14s",
                   "Appels","Temps total","Temps moyen",
                   "o(n*log(n))");
    Ecran.formater("%12s%14s%22s%14s\n",
                   "Appels","Temps total","Temps moyen",
                   "o(n*log(n))");
    int [] t = new int[1000000];
    Random r = new Random(0);
    double max = 1000000000.0;
    for ( int n = ni ; n <= nf ; n = n+inc ) {
      Ecran.formater("%10d",n);
      { { r.setSeed(0);
          Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
          mntr.temps = temps*1000;
          mntr.lancement();
          long i = 0;
          long ti = System.nanoTime();
          do {
            initRandCroissant(n,t,r);
            triBulle(n,t);
            i++; }
          while ( mntr.enCours );
          long tl = System.nanoTime()-ti;
          r.setSeed(0);
          long tiGen = System.nanoTime();
          long j = 0;
          do {
            initRandCroissant(n,t,r);
            j++; }
          while ( j < i );
          long tGen = System.nanoTime()-tiGen;
          tl -= tGen;
          Ecran.formater("%12d%14d%22.3f%14.4f",
                         i,tl,(double) tl/i,
                         ((double) tl/i)/((double) n*n)); }
        { r.setSeed(0);
          Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
          mntr.temps = temps*1000;
          mntr.lancement();
          long i = 0;
          long ti = System.nanoTime();
          do {
            initRandCroissant(n,t,r);
            triBulleOptimise(n,t);
            i++; }
          while ( mntr.enCours );
          long tl = System.nanoTime()-ti;
          r.setSeed(0);
          long tiGen = System.nanoTime();
          long j = 0;
          do {
            initRandCroissant(n,t,r);
            j++; }
          while ( j < i );
          long tGen = System.nanoTime()-tiGen;
          tl -= tGen;
          Ecran.formater("%12d%14d%22.3f%14.4f",
                         i,tl,(double) tl/i,
                         ((double) tl/i)/((double) n*n)); }
        { r.setSeed(0);
          Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
          mntr.temps = temps*1000;
          mntr.lancement();
          long i = 0;
          long ti = System.nanoTime();
          do {
            initRandCroissant(n,t,r);
            triSelection(n,t);
            i++; }
          while ( mntr.enCours );
          long tl = System.nanoTime()-ti;
          r.setSeed(0);
          long tiGen = System.nanoTime();
          long j = 0;
          do {
            initRandCroissant(n,t,r);
            j++; }
          while ( j < i );
          long tGen = System.nanoTime()-tiGen;
          tl -= tGen;
          Ecran.formater("%12d%14d%22.3f%14.4f",
                         i,tl,(double) tl/i,
                         ((double) tl/i)/((double) n*n)); }
        { r.setSeed(0);
          Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
          mntr.temps = temps*1000;
          mntr.lancement();
          long i = 0;
          long ti = System.nanoTime();
          do {
            initRandCroissant(n,t,r);
            triSelectionOptimise(n,t);
            i++; }
          while ( mntr.enCours );
          long tl = System.nanoTime()-ti;
          r.setSeed(0);
          long tiGen = System.nanoTime();
          long j = 0;
          do {
            initRandCroissant(n,t,r);
            j++; }
          while ( j < i );
          long tGen = System.nanoTime()-tiGen;
          tl -= tGen;
          Ecran.formater("%12d%14d%22.3f%14.4f",
                         i,tl,(double) tl/i,
                         ((double) tl/i)/((double) n*n)); }
        { r.setSeed(0);
          Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
          mntr.temps = temps*1000;
          mntr.lancement();
          long i = 0;
          long ti = System.nanoTime();
          do {
            initRandCroissant(n,t,r);
            triInsertion(n,t);
            i++; }
          while ( mntr.enCours );
          long tl = System.nanoTime()-ti;
          r.setSeed(0);
          long tiGen = System.nanoTime();
          long j = 0;
          do {
            initRandCroissant(n,t,r);
            j++; }
          while ( j < i );
          long tGen = System.nanoTime()-tiGen;
          tl -= tGen;
          Ecran.formater("%12d%14d%22.3f%14.4f",
                         i,tl,(double) tl/i,
                         ((double) tl/i)/((double) n*n)); }
        { r.setSeed(0);
          Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
          mntr.temps = temps*1000;
          mntr.lancement();
          long i = 0;
          long ti = System.nanoTime();
          do {
            initRandCroissant(n,t,r);
            triFusion(n,t);
            i++; }
          while ( mntr.enCours );
          long tl = System.nanoTime()-ti;
          r.setSeed(0);
          long tiGen = System.nanoTime();
          long j = 0;
          do {
            initRandCroissant(n,t,r);
            j++; }
          while ( j < i );
          long tGen = System.nanoTime()-tiGen;
          tl -= tGen;
          Ecran.formater("%12d%14d%22.3f%14.4f",
                         i,tl,(double) tl/i,
                         ((double) tl/i)/((double) n*Math.log(n))); }
        { r.setSeed(0);
          Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
          mntr.temps = temps*1000;
          mntr.lancement();
          long i = 0;
          long ti = System.nanoTime();
          do {
            initRandCroissant(n,t,r);
            triRapide(n,t);
            i++; }
          while ( mntr.enCours );
          long tl = System.nanoTime()-ti;
          r.setSeed(0);
          long tiGen = System.nanoTime();
          long j = 0;
          do {
            initRandCroissant(n,t,r);
            j++; }
          while ( j < i );
          long tGen = System.nanoTime()-tiGen;
          tl -= tGen;
          Ecran.formater("%12d%14d%22.3f%14.4f\n",
                         i,tl,(double) tl/i,
                         ((double) tl/i)/((double) n*Math.log(n))); } } }
  }
  
/* Programme principal                           */

  public static void main(String [] args) {
    int [] t = new int[250];
    Random r = new Random(0);
    double max = 1000000000.0;
    initRand(250,t,r,max);
    for ( int i = 0 ; i < 250 ; i++ )
      Ecran.afficherln(t[i]);
    Ecran.sautDeLigne();
    initRandCroissant(250,t,r);
    for ( int i = 0 ; i < 250 ; i++ )
      Ecran.afficherln(t[i]);
    Ecran.sautDeLigne();
    initRandQuasiCroissantPV(250,t,250,r);
    for ( int i = 0 ; i < 250 ; i++ )
      Ecran.afficherln(t[i]);
    Ecran.sautDeLigne();
    initRandQuasiCroissantPC(250,t,62,r);
    for ( int i = 0 ; i < 250 ; i++ )
      Ecran.afficherln(t[i]);
    Ecran.sautDeLigne();

  //  testsTri(60,2,2,1);
  //  testsTri(60,2,100,1);
  //  testsTri(10,101,1000,1);
  //  testsTri(10,10,10000,10);
  //  testsTri(10,100,100000,100);
  //  testsTri(10,1000,250000,1000);
  //  testsTri(10,10000,500000,10000);
  //  testsTri(10,50000,1000000,50000);
  }
}