/* Tri par fusion d'un tableau d'entiers      */

import java.util.Random;

public class TriRapide {

  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 n 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 void initRandCroissant(int [] t,int deb,int n,long seed,int fact) {
    Random r = new Random(seed);
    t[deb] =(int) (r.nextDouble()*fact);
    for ( int i = 1 ; i < n ; i++ ) {
      t[i+deb] = t[i+deb-1] + (int) (r.nextDouble()*fact); }
  }

/* 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 creation d'un tableau de n int    */
/* initialise avec des valeurs tirees au sort    */
/* dans l'intervalle [0,max]                     */
/* avec initialisation du generateur de nombres  */
/* aleatoires a la valeur seed                   */
  
  static int [] initRand(long seed,int n,int max) {
    Random r = new Random(seed);
    int [] t = new int[n];
    for ( int i = 0 ; i < t.length ; i++ ) {
      t[i] =(int) (r.nextDouble()*(max+1)); }
    return t;
  }

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

/* Fonction de reorganisation d'un tableau       */
/* d'entiers des indices indi a indf inclus      */
/* par replacage a gauche de toutes les valeurs  */
/* plus petites que t[pivot], a droite de toutes */
/* les valeurs plus grandes que t[pivot]         */
/* et au centre de toutes les valeurs egales     */
/* a t[pivot]                                    */
/* Retourne l'indice de la valeur d'indice       */
/* maximum, apres replacage, de toutes           */
/* les valeurs egales a t[pivot]                 */

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

/* Fonction de tri rapide par ordre croissant    */
/* d'un tableau d'int des indices                */
/* indi a indf compris                           */
/* Méthode de choix du pivot : Valeur située     */
/* à l'indice moyen de indi et indf              */
/* t    : Le tableau d'int à trier               */
/*        par ordre croissant                    */
/* indi : L'indice initial des valeurs à trier   */
/* indf : L'indice final des valeurs à trier     */

  static void triRapide(int [] t,int indi,int indf) {
    int nbVal = indf-indi+1;
    if ( nbVal > 1 ) {
      if ( nbVal == 2 ) {
        if ( t[indf] < t[indi] ) {
          int aux = t[indi];
          t[indi] = t[indf];
          t[indf] = aux; } }
        else {
        int pivot = (indi+indf)>>1;
        int iMedian = pivotage(t,indi,indf,pivot);
        triRapide(t,indi,iMedian-1);
        triRapide(t,iMedian+1,indf); } }
  }

/* Fonction de tri rapide par ordre croissant    */
/* d'un tableau d'int                            */
/* Pivot choisi : Valeur médiane du tableau      */
/* t : Le tableau d'int à trier                  */
/*     par ordre croissant                       */

  static void triRapide(int [] t) {
    triRapide(t,0,t.length-1);
  }

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

  public static void main(String [] args) {
    int [] t = initRand();
    Ecran.afficherln("Tableau initial");
    affichageTableau(t);
    triRapide(t);
    Ecran.afficherln("Tableau trié");
    affichageTableau(t);
    Ecran.sautDeLigne();
    Ecran.afficherln("Génération d'un tableau de 100000 valeurs");
    t = initRand(111,100000,100000000);
    Ecran.afficherln("Ce tableau est trié  : ",estTrie(t));
    Ecran.afficherln("Somme de ses valeurs : ",somme(t));
    triRapide(t);
    Ecran.afficherln("Réalisation du tri");
    Ecran.afficherln("Ce tableau est trié  : ",estTrie(t));
    Ecran.afficherln("Somme de ses valeurs : ",somme(t));
  }
}