/* Auteur: Nicolas JANEY          */
/* nicolas.janey@univ-fcomte.fr   */
/* Fevrier 2005                   */

public class TriInsertionEnConsole {

  /* Fonction de recherche de la position d'insertion     */
  /* d'une valeur a l'interieur d'un tableau              */
  /* ind : indice de la valeur dont on calcule            */
  /*       la position d'insertion                        */
  /* t   : tableau ou la position d'insertion             */
  /*       est recherchee                                 */

  public static int indiceInsertion(int [] t,int v,int imax) {
  /* Definition d'une variable entiere de recherche            */
  /* de la position d'insertion (initialisee a 0)              */
    int i = 0;
  /* La boucle de recherche s'execute tant que la valeur       */
  /* a l'indice courant est plus petite que la valeur          */
  /* que l'on souhaite inserer et que l'on a pas depasse       */
  /* de 1 l'indice maximum de recherche                        */
    while ( ( t[i] < v ) && ( i <= imax ) )
  /* L'indice de recherche est incremente de 1                 */
      i++;
  /* Resultat : i                                              */
    return(i);
  }

  /* Fonction de decalage d'une cellule vers la droite    */
  /* d'une partie d'un tableau d'entiers                  */
  /* t   : Tableau ou le decalage est realise             */
  /* ideb : Indice de la premiere valeur a decaler        */
  /* ifin : Indice de la derniere valeur a decaler        */

  public static void decalage(int [] t,int ideb,int ifin) {
  /* Le decalage est effectue a rebour (de l'indice            */
  /* final a l'indice initial par pas de -1                    */
    for ( int i = ifin ; i >= ideb ; i-- )
      t[i+1] = t[i];
  }

  /* Fonction de tri par insertion                        */
  /* t : tableau a trier                                  */

  public static void triInsertion(int [] t) {
    int aux;
  /* Pour tous les indices de 1 au dernier indice              */
  /* du tableau a trier                                        */
    for ( int i = 1 ; i < t.length ; i++ ) {
  /* Determination de la position d'insertion de l'element     */
  /*  d'indice i dans la partie du tableau deja triee          */
      int indice = indiceInsertion(t,t[i],i-1);
  /* Si la position d'insertion est differente                 */
  /* de la position actuelle                                   */
      if ( indice != i ) {
  /* Memorisation de t[i] dans une variable auxiliaire         */
        aux = t[i];
  /* On realise le decalage                                    */
        decalage(t,indice,i-1);
  /* Insertion                                                 */
        t[indice] = aux; } }
  }

  /* Fonction de creation d'un tableau d'entiers          */
  /* tires au hasard                                      */
  /* taille : nombre d'entiers du tableau                 */
  /* max    : valeur maximale des entiers tires au sort   */

  public static int [] initTableau(int taille,int max) {
    int [] t = new int[taille];
    for ( int i = 0 ; i < t.length ; i++ )
      t[i] =(int) (Math.random()*(max+1));
    return(t);
  }

  /* Fonction d'affichage d'un tableau d'entiers          */
  /* t : tableau dont les valeurs doivent etre affichees  */

  public static void afficheTableau(int [] t) {
    int i;
    for ( i = 0 ; i < t.length ; i++ )
      Console.out.print(t[i]+" ");
    Console.out.println();
  }

  /* Fonction principale                                  */

  public static void main(String [] args) {
    Console.setTitle("TriInsertion");
  /* Lecture au clavier des donnees initiales                  */
    Console.out.print("Taille du tableau a generer et a trier : ");
    int n = Integer.valueOf(Console.in.readLine()).intValue();
    Console.out.print("Valeur maximale des entiers du tableau : ");
    int max = Integer.valueOf(Console.in.readLine()).intValue();
  /* Generation du tableau a trier tire au hasard              */
    int [] t = initTableau(n,max);
  /* Affichage du tableau non trie                             */
    Console.out.println("Tableau initial :");
    afficheTableau(t);
  /* Tri du tableau                                            */
    triInsertion(t);
  /* Affichage du tableau trie                                 */
    Console.out.println("Tableau trie :");
    afficheTableau(t);
  }
}