QUICKSORT, ALGORITHME DE TRI EN O(N LOG N)

Commentaire de gvhecke le 03/11/2003 21:56:50

Il arrive souvent de vouloir réutiliser un même algorithme pour manipuler des structures différentes. Par exemple, trier un vercteur d'entier (int), un vecteur de réels (double), de nombres à virgule flottante (float), de string de caractère (char* ou char[]).

Il serait bien bête de devoir réimplenter à chaque fois une nouvelle fonction alors que dans l'ensemble, le code reste identique. Il n'y a que le type des variables que l'on manipule qui diffère (une fois int, une autre fois double ou float...)

Afin de permettre ce genre de chose, le language c++, permet en plaçant la ligne template <classe Type> de généraliser l'usage d'une fonction ou d'une class.

Dans l'exemple ci-dessus, j'ai coder la fonction QuickSort dans une classe (généralisée par l'usage de la ligne template <class T>). Le vecteur peut alors être de type T. Pour que cela fonctionne il faut que les opérateur ">" et "<" ait été défini pour les objet de class T. s'il on veut pouvoir trier des vecteur de string par ordre alphabétique, il faut avoir défini les opérateur "<" et ">" pour les string.

définition d'une fonction généralisée:
==========================
template <class Type>
type_retour nom_Fonction (Type variable1, Type variable2, ...);

définition d'une classe généralisée:
=========================
template <class Type>
class MaClasse
{
  public:
      MaClasse(); //constructeur
      ~MaClasse(); //Destructeur
      Type& NomFonction(const Type& var); //expl de fonction membre
      ...
  private: //membre, champs de ma classe
     Type membre1; //variable de type Type
     Type* pointeurVersMembre2; //pointeur vers une var de type Type
     int AutreMembre;
     ...
};

template <class Type>
MaClasse<Type>::MaClasse() {...} //définition du constructeur

template <class Type>
Type& MaClasse<Type>::NomFonction(const Type& var)
{...} //exemple de fonction membre d'une classe


Déclaration d'une variable MaClasse de type int:
===================================
MaClasse<int> var;

Déclaration d'un meme objet pour le type float:
==================================
MaClasse<float> var;


Voilà.

J'espère que ca t'éclairera.

Geofrey