C++ : TP 4 - Tris de vecteurs

© D. Mathieu     mathieu@romarin.univ-aix.fr
I.U.T.d'Aix en Provence - Département Informatique
Créé le 10/01/2000 - Dernière mise à jour : 25/01/2001

Remarques préliminaires :

Sommaire

Tri par insertion
   Version a  exo_01a
   Version b  exo_01b
   Version c  exo_01c
    Utilisation de la fonction insert()  exo_01d
    Utilisation de la fonction sort()  exo_01e
 exo_01
Tri à bulles
   Version de base  exo_02a
    Première amélioration  exo_02b
    Deuxième amélioration  exo_02c
    Tri à bulles "aller-retour"  exo_02c
 exo_02
Quick-sort  exo_03
Solution la plus simple ...  exo_04

Tri par insertion

exo_01
    La première méthode de tri étudiée ici permet de conserver au vecteur sa propriété d'être trié pendant toute la durée de sa construction (invariant de boucle !). Cette méthode est connue sous le nom de tri par insertion.

    Recopier le fichier dirvector/exo_04.cxx dans le fichier exo_01.cxx. Dans l'espace de noms anonyme, ne conserver que la déclaration de classdef et la fonction EditVString(). Supprimer Exo_04().

    Les différentes versions de la fonction Exo_01() seront constituées d'une boucle dans laquelle :

    Enfin le vecteur trié est édité en utilisant EditVString().

    L'insertion de la ligne peut être faite de multiples façons qui devront être testées, successivement.

exo_01a

    Dans la fonction Exo_01a(), allonger le vecteur d'une unité pour pouvoir y ranger la nouvelle chaîne en utilisant la fonction resize(). Si aucune chaîne n'a encore été insérée, ajouter la chaîne lue et passer à la boucle suivante. Dans le cas contraire, rechercher, à partir de la fin du vecteur, la position de la chaîne lue en utilisant un indice de type CVString::size_type.

    Utiliser un schéma alternatif en sortie de boucle.

    Dans le fichier Makefile, modifier la cible clean pour qu'elle efface aussi les exécutables à 3 caractères après le _ : exo_01a par exemple.

    Compiler et tester.

Corrigés : exo_01.cxx      -      Makefile

Sommaire

exo_01b

    Toujours dans le fichier exo_01.cxx, recopier la fonction Exo_01a() dans la fonction Exo_01b(). Pour allonger le vecteur d'une unité, y ranger la nouvelle chaîne au moyen de la fonction push_back(). Modifier la fonction Exo_01b() en conséquence. Remarquer que cela ne fait que déplacer, sans le résoudre, le probleme du vecteur vide.

    Compiler et tester.

Corrigés : exo_01.cxx

Sommaire

exo_01c

    Après avoir recopié la fonction Exo_01b() dans Exo_01c(), remplacer le type de l'indice par un type int. Cette modification permet à i de prendre des valeurs négatives et simplifie beaucoup le programme [1].

    Vous pouvez enfin, dans cette version, remplacer le schéma alternatif final par l'utilisation de l'opérateur ?: ou de la fonction max (i, j) qui renvoie le plus grand de deux entiers. Il y a même encore plus simple, à chercher ...

    Compiler et tester.

Corrigés : exo_01.cxx

Sommaire

Utilisation de la fonction insert()

exo_01d

    Recopier la fonction Exo_01c() dans Exo_01d(). Au lieu de commencer par augmenter la taille du vecteur avant de placer la nouvelle valeur, il est plus simple de rechercher la position à laquelle la nouvelle chaîne doit être placée, puis l'insérer au moyen de la fonction membre insert(), analogue à celle des strings :
 
ident.insert (Pos, Valeur);

où Pos est la position de l'itérateur à laquelle l'insertion de la Valeur doit être faite : une copie de Valeur est placée devant l'élément désigné par Pos.

    Compiler et tester.

Corrigés : exo_01.cxx

Sommaire

Utilisation de la fonction sort()

exo_01e

    La bibliothèque C++ offre un grand nombre d'outils permettant la manipulation des conteneurs, parmi lesquels plusieurs fonctions de tri. Sauf cas particulier, l'utilisateur a tout intérêt (et toute sécurité) à utiliser les algorithmes déjà implémentés (bien et efficacement) plutôt que de les réécrire lui-même (mal et faux !).

    Réécrire l'algorithme en utilisant la fonction générique sort() à laquelle il suffit de passer commes paramètres données :

    Compiler et tester.

Corrigés : exo_01.cxx

Sommaire

Tri à bulles

exo_02
    Il est fréquent qu'il y ait à trier ou retrier un vecteur déjà construit. Parmi les méthodes disponibles dans ce type de problème, nous ne nous interesserons ici qu'à celles ne nécessitant pas la création d'un autre vecteur, intermédiaire ou résultat. Il s'agit donc de trier le vecteur sur lui-même (la méthode dite du quick-sorti, déjà étudiée comme illustration de la récursivité appartient au même ensemble de méthodes et sera envisagée plus loin).

    La méthode du tri par remontée des bulles, ou plus simplement tri à bulles, consiste à balayer le vecteur du début à la fin en comparant les couples d'éléments adjacents et en les permutant s'ils ne sont pas ordonnés. Ce premier passage a pour effet d'amener la plus grande valeur en fin de fichier. Le balayage est recommencé sur les N-1 premiers éléments, puis sur les N-2, etc..., jusqu'à ce que le vecteur soit entièrement trié.

    La première partie de tous les exercices suivants consistera à charger le vecteur à partir du fichier, préalablement à toute opération de tri.

exo_02a

    Copier le fichier exo_01.cxx dans exo_02.cxx et supprimer toutes les fonctions Exo_01?() sauf Exo_01a().

    Trier le vecteur par ordre croissant comme indiqué ci-dessus.

    Compiler et tester.

Corrigés : exo_02.cxx

Sommaire

Première amélioration

exo_02b

    Lorsqu'un balayage du vecteur a été effectué sans qu'aucune permutation n'ait été effectuée, il est inutile de continuer : le vecteur est trié. Cette première amélioration est particulièrement sensible lorsque le vecteur original est lui-même trié, un seul passage étant nécessaire.

    Effectuer les modifications (un booléen peut être utilisé).

    Compiler et tester.

Corrigés : exo_02.cxx

Sommaire

Deuxième amélioration

exo_02c

    A chaque parcours, la tranche de vecteur parcourue est raccourcie de l'élément terminal. Or il arrive fréquemment que plusieurs éléments de la fin de la tranche soient déjà ordonnés entre eux. La tranche de vecteur peut donc en une seule fois être raccourcie de cette séquence. L'amélioration demandée ici consiste à raccourcir le vecteur jusqu'à la position de la dernière permutation effectuée lors du balayage précédent. Il s'avère que le booléen utilisé dans l'exercice précédent devient inutile.

    Faire les modifications.

    Compiler et tester.

Corrigés : exo_02.cxx

Sommaire

Tri à bulles "aller-retour"

exo_02d

    On remarque qu'en un seul passage, la plus grande valeur est amenée à la fin du vecteur. En revanche, si le plus petit élément est en dernière position, il ne remonte que d'une seule position à chaque balayage. L'idée est donc d'alterner les balayages du début vers la fin et de la fin vers le début. A chaque fois, le vecteur est raccourci à la dernière permutation effectuée, soit en fin, soit en début de vecteur.

    Faire les modifications.

    Compiler et tester.

Corrigés : exo_02.cxx

Sommaire

Quick-sort

exo_03

    Vous avez étudié la méthode récursive de quick-sort en algorithmique avec réalisation en Ada. Il vous est demandé de la traduire en C++. La principale difficulté est l'impossibilité d'imbriquer des fonctions les unes dans les autres.

    Compiler et tester.

Corrigés : exo_03.cxx

Sommaire

Solution la plus simple ...

exo_04

    Après avoir chargé le vecteur à partir du fichier, utiliser la fonction générique sort() pour le trier par ordre croissant.

    Compiler et tester.

Corrigés : exo_04.cxx

Sommaire

Téléchargement des corrigés :

tptrivect.zip

Chemins d'accès aux sources des corrigés :

~mathieu/PARTAGE/src/tp/tpC++/tptrivect/dirtrivect

[1] Cette simplification rend aussi le programme faux !!! En effet, si on suppose le type int codé sur 2 octets, les valeurs permises appartiennent à [-32768, +32767]. Les valeurs permises par le type unsigned int (ou size_type) appartiennent à l'intervalle [0, 65536]. En conséquence, l'algorithme est faux dès que le vecteur contient plus de 32767 éléments, ce qui est parfaitement possible dans la réalité (mais pas dans le contexte de ce TP!).

© D. Mathieu     mathieu@romarin.univ-aix.fr
I.U.T.d'Aix en Provence - Département Informatique