import java.io.*;
import java.lang.*;
import java.util.*;

class Tri {
         // \esc{Tri par sélection, page~\pageref{prog:tri-selection}}

  final static int N = 10;

  static int[] a = new int[N];          // \esc{Le tableau à trier} 

  static void Initialisation() { // \esc{On tire au sort des nombres} 
                                    // \esc{entre 0 et 127, en initialisant} 
                                    // \esc{le tirage au sort sur l'heure} 
      for (int i = 0; i < N; ++i)
          a[i] = (int) (Math.random() * 128);
  }

  static void Impression() {
      for (int i = 0; i < N; ++i)
          System.out.print (" " + a[i] + " ");
      System.out.println ("");
  }

  static void TriSelection() {
      int   min, t;

      for (int i = 0; i < N - 1; ++i) {
          min = i;
          for (int j = i+1; j < N; ++j)
             if (a[j] < a[min])
                 min = j; 
          t = a[min]; a[min] = a[i]; a[i] = t;
      }
  }

  static void TriBulle() {
  // \esc{Tri bulle, voir page \pageref{prog:tri-bulle}} 

    int   t;

    for (int i = N-1; i >= 0; --i) 
        for (int j = 1; j <= i; ++j)
            if (a[j-1] > a[j]) {
                t = a[j-1]; a[j-1] = a[j]; a[j] = t;
            }
  }

  static void TriInsertion() {
  // \esc{Tri par insertion, voir page \pageref{prog:tri-insertion}} 
    int   j, v;

    for (int i = 1; i < N; ++i) {
        v = a[i]; j = i;
        while (j > 0  &&  a[j-1] > v) {
            a[j] = a[j-1]; 
            --j;
        }
        a[j] = v;
    }
  }

  static void TriShell() {
  // \esc{Tri Shell, voir page \pageref{prog:tri-shell}} 
    int   h;

    h = 1; do 
       h = 3*h + 1; 
    while ( h <= N );
    do {
        h = h / 3;
        for (int i = h; i < N; ++i)
            if (a[i] < a[i-h]) {
                int   v = a[i], j = i;
                do {
                    a[j] = a[j-h];
                    j = j - h;
                } while (j >= h  &&  a[j-h] > v);
                a[j] = v;
            }
    } while ( h > 1);
  }

  public static void main(String args[]) {

      Initialisation();   // \esc{On lit le tableau}
      Impression();       // \esc{et on l'imprime}
      TriSelection();     // \esc{On trie}
      Impression();       // \esc{On imprime le résultat} 
      TriBulle();      
      Impression();    
      TriInsertion();
      TriShell();
      Impression();    
  }
}