template <class T> void triBulleIter(T& v)
{
    const int N=v.size();

    for(int i=0;i<N;++i)
    {
      for(int j=1;j<N-i;++j)
      {
          if(v[j]<v[j-1])
            std::swap(v[j],v[j-1]);
      }
    }
}

template <class T>
void triBulleRecur(T& v)
{
    static int n=0;

    const int N=v.size();
    const int N2=N-1-n;

    for(int i=0;i<N2;++i)
    {
      if(v[i]>v[i+1])
                std::swap(v[i],v[i+1]);
    }

    n++;

    if(N-n>1)
      triBulleRecur(v);
    else
      n=0;
}

template <class T> void triInsertion(T& v) 
{
    int p=0;
    typename T::value_type x;

    const int N=v.size();

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

template <class T> void triRapide(T& v, int p, int r)
{
        if(p<r)
        {
          int q = partitionner(v, p, r);
          triRapide(v, p, q);
          triRapide(v, q+1, r);
        }
}
 
template <class T> int partitionner(T& v, int p, int r) 
{
    typename T::value_type pivot = v[p], i = p-1, j = r+1;

        while(1) 
      {
          do
          {
            j--;
          } while(v[j] > pivot);

          do
          {
                        i++;
          } while(v[i] < pivot);

                if(i<j) 
            {
                std::swap(v[i],v[j]);
                }
                else
                break;
        }
        return j;
}

template <class T>void triSelection(T& v)
{
    int min=0;
    const int N=v.size();
    for (int i = 0; i < N-1; ++i)
    {
        min=i;
        for (int j=i+1; j<N; ++j)
        {
            if(v[j]<v[min])
                min=j;
        }

        if(min!=i)
            std::swap(v[i],v[min]);
    }
}

template <class T> void triShellPhase(T& v, int gap) 
{
    typename T::value_type value;
    int j=0;

    const int N=v.size();

    for (int i = gap; i < N; ++i) 
    {
        value = v[i];
        for (j = i - gap; j >= 0 && v[j] > value; j -= gap) {
            v[j + gap] = v[j];
        }
        v[j + gap] = value;
    }
}
 
template <class T>void triShell(T& v) 
{
    const int gaps[]={1, 4, 10, 23, 57, 132, 301, 701};
    const int N=sizeof(gaps)/sizeof(gaps[0])-1;
 
    for (int sizeIndex = N;sizeIndex >= 0;--sizeIndex)
        triShellPhase(v, gaps[sizeIndex]);
}

template <class T>
void triPanier(T& v)
{   
    typedef typename T::value_type value_type;
    typedef typename std::map<value_type,int>::iterator map_it;

    const int N=v.size();
    std::map<value_type,int> tmp;

    for(int i=0;i<N;++i)
      tmp[v[i]]++;

    int index=0;
    map_it ite=tmp.end();
    for(map_it it=tmp.begin();it!=ite;++it)
    {
      for(int j=0;j<(*it).second;++j)
          v[index++]=(*it).first;
    }

}