/* Tri par selection avec min-max applique        */
/* a un tableau d'entiers                         */

import java.util.Random;

public class TriSelectionOptimise {

  static long somme(int [] t) {
    long total = 0L;
    for ( int i = 0 ; i < t.length ; i++ ) {
      total = total+t[i]; }
    return total;
  }

  static boolean estTrie(int [] t) {
    boolean trie = true;
    int i = 0;
    while ( trie && ( i < t.length-1 ) ) {
      if ( t[i] > t[i+1] )
        trie = false;
      i++; }
    return trie;
  }

/* 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.formater("%4d",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 n 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+1));
      i2 =(int) (r.nextDouble()*(n+1));
      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 tirees au sort    */
/* dans l'intervalle [0,1000[                    */
  
  static int [] initRand() {
    int [] t = new int[10];
    for ( int i = 0 ; i < t.length ; i++ ) {
      t[i] =(int) (Math.random()*1000.0); }
    return t;
  }

////////////////////////////////////////////////////

/* 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) {
    iMax = ni;
    iMin = ni;
    for ( int i = ni+1 ; i <= nf ; i++ ) {
      if ( t[i] < t[iMin] ) {
        iMin = i; }
      if ( t[i] > t[iMax] ) {
        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)/2;
    int ni = 0;
    int nf = t.length-1;
    for ( int i = 0 ; i < ne ; i++ ) {
      indiceMinimumEtMaximum(ni,nf,t);
      Ecran.afficherln(iMin," ",iMax);
      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; } } }
      affichageTableau(t);
      ni++;
      nf--; }
    if ( t.length%2 == 0 ) {
      if ( t[ni] > t[nf] ) {
        aux = t[ni];
        t[ni] = t[nf];
        t[nf] = aux; }
    }
  }

////////////////////////////////////////////////////
  
/* Programme principal                            */

  public static void main(String [] args) {
    int [] t = initRand();
    Ecran.afficherln("Tableau initial");
    affichageTableau(t);
    triSelectionOptimise(t);
    Ecran.afficherln("Tableau trié");
    affichageTableau(t);
  }
}