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

public class TriInsertion {

/* 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 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 et retour                */
/* de la position d'un int dans un tableau d'int  */
/* trié par ordre croissant et restreint          */
/* aux indices 0 a n-1 inclus                     */
/* (n premières valeurs du tableau)               */
/* v : Valeur int recherchée                      */
/* n : Nombre de valeurs initiales du tableau     */
/*     parmi lesquelles la recherche est réalisée */
/* t : Tableau trié d'entiers de recherche        */

  static int positionInsertion(int v,int n,int [] t) {
    int p = n;
    do {
      p--; }
    while ( ( p >= 0 ) && ( v < t[p] ) );
    return p+1;
  }

/* Fonction de décalage de une cellule            */
/* vers la droite du contenu des cellules         */
/* d'indice indi à indf inclus                    */
/* d'un tableau d'int                             */
/* indi : L'indice initial de décalage            */
/* indf : L'indice final de décalage              */
/* t : Le tableau d'int où le décalage            */
/*     est réalisé                                */

  static void decalage(int indi,int indf,int [] t) {
    for ( int i = indf ; i >= indi ; i-- ) {
      t[i+1] = t[i]; }
  }

/* Fonction de tri "par insertion"                */
/* par ordre croissant des valeurs                */
/* contenues dans un tableau d'int                */
/* t : Le tableau d'int à trier                   */
/*     par ordre croissant                        */

  static void triInsertion(int [] t) {
    for ( int i = 1 ; i < t.length ; i++ ) {
      int p = positionInsertion(t[i],i,t);
      if ( p != i ) {
        int v = t[i];
        decalage(p,i-1,t);
        t[p] = v; } }
  }

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

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