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

public class TriInsertion {

/* Methode d'affichage des valeurs contenues     */
/* dans un tableau de int                        */
  
  static void affichageTableau(int [] t) {
    int i;
    for ( i = 0 ; i < t.length ; i = i+1 ) {
      Ecran.afficher(t[i]," "); }
    Ecran.sautDeLigne();
  }

/* Methode de creation d'un tableau de 10 int    */
/* initialise avec des valeurs tirees au sort    */
/* entre 0 et 1000 inclus                        */
  
  static int [] initRand() {
    int [] t = new int[10];
    int i;
    for ( i = 0 ; i < t.length ; i = i+1 ) {
      t[i] =(int) (Math.random()*1001.0); }
    return t;
  }
  
///////////////////////////////////////////////////
  
/* Methode de recherche de la position           */
/* d'un entier v dans un tableau d'entiers       */
/* restreint aux indices 0 a l-1 inclus          */

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

/* Methode 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) {
    int i;
    for ( i = indf ; i >= indi ; i = i-1 ) {
      t[i+1] = t[i]; }
  }

/* Methode de tri par insertion d'un tableau     */
/* d'entiers                                     */

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

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

  public static void main(String [] args) {
    int [] t;
    t = initRand();
    affichageTableau(t);
    triInsertion(t);
    affichageTableau(t);
  }
}