/* Tri naif applique a un tableau d'entiers      */

import java.util.Random;

public class TriNaif {

  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.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+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 n int    */
/* initialise avec des valeurs tirees au sort    */
/* entre 0 et 1000 inclus                        */
  
  static int [] initRand(int n,int max) {
    int [] t = new int[n];
    for ( int i = 0 ; i < t.length ; i++ ) {
      t[i] =(int) (Math.random()*(max+1)); }
    return t;
  }

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

/* 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;
    for ( int i = 0 ; i < t.length ; i++ )
      tc[i] = t[i];
    for ( int i = 0 ; i < t.length ; i++ ) {
      indice = indf;
      for ( int j = indf-1 ; j >= 0 ; j-- ) {
        if ( tc[j] < tc[indice] ) {
          indice = j; } }
      t[i] = tc[indice];
      tc[indice] = tc[indf];
      indf--; }
  }

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

  public static void main(String [] args) {
    int [] t;
    t = initRand(111111,100000000);
    Ecran.afficherln(estTrie(t)," ",somme(t));
    //affichageTableau(t);
    triNaif(t);
    Ecran.afficherln(estTrie(t)," ",somme(t));
    //affichageTableau(t);
  }
}