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

import java.io.*;

public class TriInsertionBis {
  static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
  
  /* Fonction de recherche de la position d'insertion     */
  /* d'une valeur du tableau a l'interieur du 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 ind,int [] t) {
  /* 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 ou egale          */
  /* que la valeur que l'on souhaite inserer et que       */
  /* l'indice courant est strictment inferieur a l'indice */
  /* de la valeur a inserer                               */
  /* -> La boucle s'arrete quand on a trouve la premiere  */
  /* valeur du tableau t superieure strictement           */
  /* a la valeur a inserer ou que l'on est a l'indice     */
  /* de la valeur elle-meme                               */
    while ( ( t[i] <= t[ind] ) && ( i < ind ) )
  /* L'indice de recherche est incremente de 1            */
      i++;
  /* Resultat : i                                         */
    return(i);
  }
  
  /* Fonction d'insertion d'une valeur du tableau         */
  /* a sa position dans l'ordre de tri                    */
  /* pos : Position d'insertion                           */
  /* t   : Tableau ou l'insertion est realisee            */
  /* src : Indice de la valeur a inserer                  */

  public static void insertion(int pos,int [] t,int src) {
  /* Sauvegarde de la valeur a inserer                    */
    int v = t[src];
  /* Decalage des valeurs du tableau t pour "faire        */
  /* une place" a la valeur a inserer                     */
  /* Le decalage est effectue a rebour (de l'indice       */
  /* final a l'indice d'insertion par pas de -1           */
    for ( int i = src ; i > pos ; i-- )
      t[i] = t[i-1];
  /* Insertion                                            */
    t[pos] = v;
  }
  
  /* Fonction de tri par insertion                        */
  /* t : tableau a trier                                  */

  public static void triInsertion(int [] t) {
  /* 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(i,t);
  /* Si la position d'insertion est differente            */
  /* de la position actuelle                              */
      if ( indice != i )
  /* On realise l'insertion                               */
        insertion(indice,t,i); }
  }
  
  /* 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++ )
      System.out.print(t[i]+" ");
    System.out.println();
  }
  
  /* Fonction principale                                  */

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