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

import java.io.*;

public class TriBulle {
  static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
  
  /* Fonction de tri a bulle                              */
  /* t : tableau a trier                                  */

  public static void triBulle(int [] t) {
  /* Definition d'un booleen pour indiquer si le tri      */
  /* est fini (initialise a zero)                         */
    boolean stop = false;
  /* Definition d'un compteur pour indiquer le nombre     */
  /* de cellules deja triees                              */
    int ind = 0;
  /* Tant que le tri n'est pas fini                       */
    while ( !stop ) {
  /* stop est affecte a vrai pour indiquer que sauf       */
  /* si au moins une permutation a lieu, le tri sera fini */
      stop = true;
  /* Boucle de parcours du tableau a la recherche         */
  /* d'une permutation. Les ind premieres cellules        */
  /* etant deja triees, la boucle commence a l'indice ind */
      for ( int i = 0 ; i < t.length-1-ind ; i++ )
  /* Test de l'occurrence d'une permutation               */
  /* entre i et i+1                                       */
        if ( t[i] > t[i+1] ) {
  /* Si une permutation a lieu, le tri ne sera pas fini   */
  /* a l'issue de la boucle for -> ajustement de stop     */
          stop = false;
  /* Permutation des elements d'indice i et i+1           */
          int v = t[i];
          t[i] = t[i+1];
          t[i+1] = v; }
  /* Une cellule de plus est triee                        */
      ind++; }
  }
  
  /* 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                                       */
    triBulle(t);
  /* Affichage du tableau trie                            */
    System.out.println("Tableau trie :");
    afficheTableau(t);
  }
}