L’algorithme du quick-sort sera étudié dans le TP de structures de données consacré aux arbres binaires et à la récursivité.

Nous présentons ici un algorithme légèrement différent de la fonction Partitionnement() (l’intervalle est ici fermé) :

template <typename T>
fonction partitionnement (tab   : in_out tableau de T, 
                          first : in     entier_naturel, 
                          last  : in     entier_naturel) renvoie entier_naturel

debut
    Declarer isUp : booleen;
    isUp <- vrai;
    Declarer pivot   : entier_naturel;
    Declarer courant : entier_naturel;
    Declarer incr    : entier;
    pivot   <- first;
    courant <- last;
    incr    <- -1;
    tant_que (pivot ne_vaut_pas courant)
    faire
        si (NON isUp ET_ALORS tab [pivot] < tab [courant]
                OU_SINON
            isUp ET_ALORS tab [courant] < tab [pivot])

            permuter (tab [pivot], tab [courant]);
            permuter (pivot, courant);
            isUp <- NON isUp;
            incr <- -incr;
        fsi
        courant <- courant + incr;
    ffaire
    renvoie pivot;

fin

Rappelons l’algorithme du quick-sort (intervalle semi-ouvert) :

template <typename T>
procedure quickSort (tab   : in_out tableau de T, 
                     beg   : in     entier_naturel, 
                     end   : in     entier_naturel)
debut
    si (beg < end)
        Déclarer pos : entier_naturel;
        pos <- partitionnement (tab, beg, end - 1);

        quickSort (tab, beg,     pos);
        quickSort (tab, pos + 1, end);
    fsi
fin

Travail à effectuer

Créer le projet QuickSort.

Dans l’espace de noms anonyme du fichier QuickSort.cpp, traduire en C++ les deux algorithmes ci-dessus.

Dans ce même espace de noms anonyme, ajouter la classe générique suivante :

    template <typename T>
    class ILessThanGen
    {
      public :
        virtual ~ILessThanGen (void) {}
        virtual bool operator () (const T &, const T &) const = 0;

    }; // ILessThanGen

Ajouter les classes TriParAgeAsc et TriParNomDesc, dérivées de la classe ILessThanGen, qui permet de comparer des Pers respectivement dans l’ordre d’ages croissants et de noms décroissants.

    class Pers
    {
        string   myNom;
        unsigned myAge;
 
      public :
        Pers (const string & Nom, unsigned Age)
            : myNom (Nom), myAge (Age) {}
 
        const string & getNom (void) const noexcept { return myNom; }
        unsigned       getAge (void) const noexcept { return myAge; }
 
    private :
        ostream & display (ostream & os)  const
        {
            return os << getAge () << " - " << getNom ();
 
        } // display()
 
      public :
        friend ostream & operator << (ostream & os, const Pers & p)
        {
            return p.display (os);
 
        }
 
    }; // Pers

Coder les fonctions génériques partitionnement() et quickSort().

Remarques

1. En C++, le passage du tableau est inutile si la tranche du tableau à traiter est décrite par des itérateurs.
2. Le type iterator nécessite d’être instancié pour être utilisé. Il ne le sera que lors de l’appel à quickSort(). On ne peut donc déclarer un paramètre de ce type sans que ce type soit un nouveau paramètre de généricité.
3. La fonction de comparaison utilisée dans la procédure partitionnement() doit être passée sous la forme d’un functor.
4. Veiller à limiter les variables locales.En particulier, lorsque c’est possible, préférer passer les itérateurs par valeur (par recopie) plutôt que d’en déclarer des instances locales.
5. Pour des raisons purement algorithmiques, les intervalles sont semi-ouverts lorsqu’ils sont passés à la fonction quickSort() et fermés lorsqu’ils sont passés à la fonction partitionnement().

Test de la fonction quickSort().

La fonction suivante est mise à votre disposition pour tester votre programme :

    void functorSort (void)
    {
        cout << "FunctorSort : \n";
 
        typedef vector <Pers> CVPers;
 
        CVPers vPers;
 
        vPers.push_back ( Pers ("Charlotte", 21));
        vPers.push_back ( Pers ("Alfred",    12));
        vPers.push_back ( Pers ("Jean",      42));
        vPers.push_back ( Pers ("Noemie",    11));
        vPers.push_back ( Pers ("Berthe",    99));
        vPers.push_back ( Pers ("Agathe",    29));
        vPers.push_back ( Pers ("Sylvain",   42));
        vPers.push_back ( Pers ("Pierre",    75));
 
        cout << "\nTri par age croissant\n\n";
 
        quickSort (vPers.begin (), vPers.end (), TriParAgeAsc ());
 
        for (const Pers & personne : vPers)
            cout << personne << '\n';
 
        cout << "\nTri par nom decroissant\n\n";
 
        quickSort (vPers.begin (), vPers.end (), TriParNomDesc ());
 
        for (const Pers & personne : vPers)
            cout << personne << '\n';
 
    } // functorSort()

Dernière remarque

Pour y stocker provisoirement la valeur du pivot, il est nécessaire de déclarer, dans le corps de la fonction, une variable locale du type de l’objet pointé.

Malheureusement, ce type n’est pas connu, il dépend du type de l’itérateur qui a servi à instancier la fonction quickSort().

Il est cependant accessible par la ligne suivante, que vous ajouterez dans la fonction :

typedef typename std::iterator_traits ::value_type Value_t;

iterator_traits est une classe générique standard dont le paramètre de généricité est un type d’itérateur, et qui exporte le type (value_type) de l’objet pointé par un itérateur de type IterType.

Elle est définie dans la bibliothèque iterator.