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

import java.io.*;

public class TriSelection {
  static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
  
  /* Fonction de recherche de l'indice du plus petit      */
  /* element d'un tableau d'entiers                       */
  /* t   : tableau ou effectuer la recherche              */
  /* deb : indice a partir duquel commencer la recherche  */
  /* fin : indice jusqu'auquel effectuer la recherche     */

  public static int indiceDuMinimum(int [] t,int deb,int fin) {
    int ind = deb;
    for ( int i = deb+1 ; i <= fin ; i++ )
      if ( t[i] < t[ind] )
        ind = i;
    return(ind);
  }

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

  public static void triSelection(int [] t) {
  /* Pour tous les indices deb jusqu'a l'anvant dernier   */
    for ( int deb = 0 ; deb < t.length-1 ; deb++ ) {
  /* Calcul de l'indice i du minimum                      */
  /* de deb jusqu'a fin du tableau                        */
      int i = indiceDuMinimum(t,deb,t.length-1);
  /* Permutation des elements d'indice i et deb           */
      int v = t[deb];
      t[deb] = t[i];
      t[i] = v; }
  }
  
  /* 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                                       */
    triSelection(t);
  /* Affichage du tableau trie                            */
    System.out.println("Tableau trie :");
    afficheTableau(t);
  }
}