// tri rapide

#include <stdlib.h>

class Elem{
public:
  int valeur;
  Elem* suivant;
  Elem(int valeur,Elem* suivant);
};

Elem::Elem(int valeur,Elem* suivant){
  this->valeur = valeur;
  this->suivant = suivant;
}

//-------------------------------------------
//           ALGORITHME DE TRI
//-------------------------------------------


void insererEnTete(Elem* e,Elem* &liste){
  //  A compléter.
}

// Attache la liste "liste2" a la fin de la liste "liste1".
void concatener(Elem* &liste1,Elem* liste2){
  // A compléter (algorithme récursif).
}

// rajoute à la liste "petits" (resp. "grands") les éléments
// de la liste "liste" plus petits (resp. grands) que le "pivot". 
void separer(int pivot,Elem* liste,Elem* &petits,Elem* &grands){
  // A compléter (algorithme récursif ou itératif).
}

// Attache l'un derrière l'autre la liste "petits",
// l'élément "pivot" et la liste "grands", et retourne
// la liste "petits".
Elem* joindre(Elem* &petits,Elem* pivot,Elem* grands){
  pivot->suivant = grands;
  concatener(petits,pivot);
  return petits;
}

// Trie la liste "liste" sur place.
void trier(Elem* &liste){
  // A compléter (algorithme récursif).
}

//-------------------------------------------
//         TEST DE L'ALGORITHME
//-------------------------------------------

#include <iostream.h>
#include <math.h>

void afficher(Elem* liste){
  Elem* courant = liste;
  while (courant != NULL){
    cout << courant->valeur << " ";
    courant = courant->suivant;
  }
  cout << endl;
}

// renvoie aléatoirement un nombre entre 0 et n. 
int hasard(int n){
  return rand() % n;
}

int main(){
  Elem* liste = NULL;
  int longueur;

  cout << "Longueur de la liste à trier : " << flush;
  cin >> longueur;

  // Génération aléatoire de la liste de nombres.
  for(int i = 0;i < longueur;i++)
    insererEnTete(new Elem(hasard(longueur),NULL),liste);
  
  cout << "Liste générée : " << flush; afficher(liste);
  
  trier(liste);
  cout << "Liste triée   : " << flush; afficher(liste);
}