/* File: trirapide.cc -- Francois -- Last modified on 11 Oct 2001
 * 	
 *      Tri rapide
 *
 */



#include <iostream.h>
#include <vector>

using namespace std;


void Echange(int & i,int & j)
{int aux = i;
i = j;
j = aux;
}

// reorganise le tableau T en fonction du pivot T[bg]
// et retourne le nouvel indice du pivot apres la reorganisation
int Pivoter(vector<int> & T,int bg,int bd)
{
int l,r,piv=T[bg];
l=bg+1;
r=bd;
while (l <= r) {
  while((l <= bd) && (T[l] <= piv)) l++;
  while((r>=0) && (T[r] > piv)) r--;
  if (l < r) {
    Echange(T[l],T[r]);
    r--; l++;
  }
}
Echange(T[r],T[bg]);
return r;
}


// Tri le tableau T entre les indices bg et bd.
// ou entre 0...T.size()-1 si bg==bd==-1
void Tri_rapide(vector<int> & T,int bg =-1,int bd =-1)
{
  if ((bg==-1) && (bd==-1)) {
    bg=0;
    bd= int(T.size())-1; // conversion en int pour autoriser le -1 en cas de 0
                          // car size() renvoie un unsigned
  }
  
int indp;
if (bg < bd) {
  indp = Pivoter(T,bg,bd);
  Tri_rapide(T,bg,indp-1);
  Tri_rapide(T,indp+1,bd);
}
}



// 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_rapide(T1);
affichetab(T1);

}