:: Enseignements :: ESIPE :: E3INFO :: 2013-2014 :: Algorithmique ::

Tris

Les TP 4 et 5 donneront lieu à un rapport qui sera à déposer, au format pdf, sur la plateforme Moodle après la prochaine séance de TP. Ce rapport contiendra les explications des algorithmes, et des tests que vous avez choisis, ainsi qu'une analyse comparative de la complexité de vos algorithmes et les diagrammes qui les illustrent.

Exercice 1 - Suites pseudo-aléatoires

Pour pouvoir tester les différentes fonctions de tris, on remplira des tableaux avec le générateur aléatoire standard du C (cf. l'exercice 1 du TP 1). Écrire une fonction void remplirTableau(int tableau[], int taille, int max) qui remplit le tableau tableau avec des valeurs pseudo-aléatoires comprises entre 0 et max-1.

Exercice 2 - Tri d'un tableau

Écrire trois fonctions permettant le tri d'un tableau d'entiers. Chaque fonction doit prendre en paramètre un tableau int tableau[] et sa taille int taille.
- tri par sélection
- tri par insertion
- tri à bulles

Exercice 3 - Tests

Comment pouvez-vous assurer que les implémentations de vos algorithmes de tri sont correctes, c'est-à-dire qu'ils trient bien tous les tableaux correctement ?
Suggérer des tests pour vérifier que vos algorithmes fonctionnent dans des cas de bornes (cas "aux limites"), pour des petits tableaux et pour des grands... et implémenter ces tests dans une ou plusieurs fonctions.

Exercice 4 - Visualisation

Ajouter deux paramètres à vos fonctions de tri afin de calculer
- le nombre de comparaisons (entre éléments à trier),
- le nombre de déplacements (nombre d'affectations des éléments à trier)
requis pour le tri du tableau. Notez qu'un échange de deux valeurs dans un tableau s'effectue par 3 déplacements.
Pour visualiser le nombre de comparaisons et de déplacements des différents algorithmes, on utilise le programme gnuplot pour tracer au format postscript des données présentes dans des fichiers.
- Créer un fichier tri.dat contenant les données à visualiser. Le fichier sera formaté de la manière suivante :
  - chaque colonne est séparée par un espace ;
  - la première colonne contiendra le nombre d'éléments dans le tableau à trier ;
  - les colonnes suivantes contiendront respectivement le nombre de comparaisons qu'il a fallu effectuer pour trier le tableau selon l'algorithme du tri par sélection, du tri par insertion, et enfin du tri à bulles.
  Ainsi, une ligne contenant les entiers 10 55 37 72 signifie que, pour trier un tableau contenant 10 valeurs, il a fallu 55 comparaisons pour le tri par sélection. 37 comparaisons pour le tri par insertion, 72 comparaisons pour le tri à bulles,
- Créer un fichier plot contenant
```
set output "tri.ps"
set terminal postscript color "landscape"
set title "nombre de comparaisons"

plot "tri.dat" using 1:2 title "tri par selection" with lines linetype 1, \
"tri.dat" using 1:3 title "tri par insertion" with lines linetype 2, \
"tri.dat" using 1:4 title "tri a bulles" with lines linetype 3
```
  Les deux premières lignes permettent de sauvegarder le résultat du tracé dans le fichier tri.ps. La troisième ligne permet de définir le titre du graphique. Les trois dernières lignes permettent de tracer trois courbes sur un même graphique. Chacune des lignes signifie que l'on veut tracer une courbe à partir du fichier tri.dat en considérant, par exemple, la première colonne comme abscisse et la troisième colonne pour ordonnée (using 1:3), et que l'on veut donner une légende à chaque courbe (title "tri par insertion"). L'option utilisée est with lines permettant de relier les points par une droite et linetype suivi d'un entier de 1 à 8 permettant de désigner la couleur du tracé.
- Taper dans un terminal gnuplot plot pour construire le graphique et gv tri.ps ou evince tri.ps pour le visualiser (les valeurs utilisées ci-dessous pour l'exemple ne sont pas nécessairement les bonnes...).
Vous commenterez les différents graphiques obtenus et comparerez les différents algorithmes de tri. Effectuez vos tests sur plusieurs copies d'un même tableau, pour apprécier les différences, ainsi que des valeurs aléatoires pouvant être relativement grandes par rapport à la taille du tableau.
Voyez-vous toutes les courbes? Essayez différents ordres de grandeurs du nombre d'éléments à trier afin de percevoir des différences plus subtiles.