/* File: triinsertion.cc -- Francois -- Last modified on 11 Oct 2001
 * 	
 *      Tri par insertion (non recursif)
 *
 */



#include <iostream>
#include <vector>

using namespace std;

// insere tab[n] (le n-eme element) a sa place dans tab[0]...tab[n-2] 
void inserer(vector<int> & tab,int n)
{
  int val, k;
  val = tab[n];
  k = n;
  while ((k>0) && (tab[k-1]>val)) {
    tab[k] = tab[k-1];
    k--;
  }
  tab[k]=val;
}

// On passe le tableau par reference: on le modifie !
void Tri_insertion(vector<int> & tab)
{
  for (int i=1;i<tab.size();i++)
    inserer(tab,i);
}



// affiche le contenu d'un tableau
void affichetab(vector<int> t)
{
  for (int i=0;i<t.size();i++) 
    cout << t[i] << " ";
  cout << endl;
}

// lit un tableau
vector<int> LireTableau()
{
  int N=0;
  cout << "Quelle taille ?";
  cin >> N;
  vector<int> res (N,0);

  for (int i=0;i<N;i++) {
    cout << "Element["<<i<<"] : ";
    cin >> res[i];
  }
  return res;
}


int main()
{
vector<int> T1;
 T1 = LireTableau();

affichetab(T1);
Tri_insertion(T1);
affichetab(T1);

}