:: Enseignements :: ESIPE :: E3INFO :: 2014-2015 :: Algorithmique ::

Tris

Le TP 4 se déroule en deux temps: 1) une première partie qui a lieu en TP et qui doit conduire au dépôt, à la fin de la séance, des codes C réalisés sur la plateforme Moodle et 2) une seconde partie, en autonomie, qui vous conduit à poursuivre des tests comparatifs et à réaliser un rapport en pdf qui devra à nouveau être déposé sur la plateforme Moodle. 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 - Tri par sélection d'un tableau

Commencer par récupérer l'archive Base.zip et extraire les fichiers dans votre répertoire de travail. Les fichiers tableau.h et tableau.c contiennent des fonctions de base sur les tableaux, les fichiers tri.h et tri.c des fonctions de tri et le fichier tp04.c contient une fonction main qui va nous permettre de tester les tris. Le ficheir Makefile permet de générer un exécutable de nom ./tp04.

Testez par make que cela fonctionne et exécutez ./tp04 pour constater que la fonction trierSelection() appelée dans tp04.c à la ligne 34 ne fonctionne pas correctement.
Allez voir dans tric.c et faites ce qu'il faut pour que le tri sélection soit correctement réalisé. Testez à nouveau l'exécution après avoir relancé le Makefile.
Dans tp04.c, changez la valeur de TAILLE_MAX en début de fichier. Par exemple, essayez avec 0: est-ce que votre fonction de tri fonctionne correctement? Essayez maintenant avec 1000: est-ce que votre fonction de tri fonctionne correctement?

Exercice 2 - Tests

Regarder à l'oeil nu si l'affichage du tableau est correct n'est pas satisfaisant dès que le nombre d'éléments dépasse une dizaine. 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.
On pourrait utiliser une fonction de tri déjà existante de la bilbiothèque C comme qsort pour vérifier si notre fonction trierSelection produit exactement le même résultat, mais on va plutôt essayer de vérifier par nous mêmes. Inspirez vous des prototypes des deux dernières fonctions de tableau.h et implémentez-les dans tableau.c pour les utiliser dans le main de tp04.c afin de tester correctement la fonction de tri par sélection (vous pourrez alors utiliser le contenu de tab_ref).
Note: int ontMemeContenuTableaux(int t1[], int t2[], int taille) retourne 1 si les éléments contenus dans les deux tableaux sont les mêmes, indépendament de leur ordre.

Exercice 3 - Implémentation d'autres tris

On peut maintenant poursuivre l'implémentation dans tri.c de nos tris dont les prototypes de fonction sont décrits dans le fichier tri.h.

Tri par insertion vu en TD
Tri Bulles Cailloux vu en TD
Tri rapide (quick sort, vu en cours)

Exercice 4 - Comptage et comparaison visuelle des tris

On souhaite maintenant pouvoir comparer les différentes fonctions de tri en nombre de comparaisons ou en nombre d'affectations effectuées. Plutôt que de modifier les fonctions déjà écrites, que nous avons testé précédement, nous allons les recopier dans des fonctions instrumentées ayant des paramètres supplémentaires qui vont nous permettre de réaliser ces mesures.

Recopiez chacune des fonctions de tri dans tri.h en les renommant avec l'extension _instr et en leur ajoutant deux paramètres permettant 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.
Par exemple:
```
void trierSelection(int tab[], int taille);
void trierSelection_instr(int tab[], int taille, int *nbComp, int *nbDepl);
```
Sur la base des fonctions de tri réalisées précédemments, implémentez dans tri.c les versions instrumentées de chacune d'entre elle.

Vous pouvez alors créer nu nouveau fichier, tp04-instr.c pour éviter de casser votre programme précédent, et ajouter les règles et dépendances nécessaires à votre fichier Makefile, pour pouvoir produire un nouvel exécutable tp04-instr dont l'execution vous affichera le nombre de comparaisons et le nombre d'affectations des tris effectués. Par exemple, pour le fichier tp04-instr.c suivant, vous aurez les compteurs du tri sélection.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#include "tableau.h"
#include "tri.h"

#define VALEUR_MAX 1000000
#define TAILLE_MAX 1000

int main(int argc, char *argv[]) {
	srand(getpid());
	int taille = TAILLE_MAX;
	int valeurMax = VALEUR_MAX;
	/* tableau de référence */
	int* tab_ref = NULL;
	/* tableau de travail */
	int* tab = NULL;
	/* compteurs */
	int nbComp = 0;
	int nbDepl = 0;

	/* allocation et initialisation de la référence avec des valeurs aléatoires */
	tab_ref = allouerTableau(taille);
	remplirTableauAleatoire(tab_ref, taille, valeurMax);
	/* allocation et initialisation du tableau de travail avec les valeurs de référence */
	tab = allouerTableau(taille);
	recopierTableau(tab_ref, tab, taille);
	/* tri du tableau de travail */
	trierSelection_instr(tab, taille, &nbComp, &nbDepl);
	printf("%d comparaisons\n", nbComp);
	printf("%d déplacements\n", nbDepl);
	/* libération des tableaux de la taille courante */
	free(tab);
	tab = NULL;
	free(tab_ref);
	tab_ref = NULL;
	
	return EXIT_SUCCESS;
}

Et il suffirait de réaliser plusieurs appels à différents tris pour avoir un comparatif du nombre de comparaisons (ou d'affectation) qu'ils nécessitent.

Pour visualiser le nombre de comparaisons et de déplacements des différents algorithmes, on va utiliser le programme gnuplot pour tracer au format postscript des données présentes dans des fichiers. Les quelques instructions suivantes devraient vous permettre de comprendre comment il fonctionne.
- 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, par exemple, 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, et 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 "with lines" permet de relier les points par une droite et linetype suivi d'un entier de 1 à 8 permet 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...).
Il vous suffit maintenant de modifier votre programme tp04-instr.c pour qu'il effectue les mesures souhaitées et réalise les affichages correspondant dans le format requis pour le fichier plot, et vous pourrez obtenir les courbes comparatives des différents algorithmes de tri. 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, avec des valeurs aléatoires 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.
En utilisant gnuplot, visualiser le nombre de comparaisons et de déplacements pour le tri rapide. Comparer avec les autres tris.
Combien d'entiers pouvez-vous trier en 10 secondes avec les différents algorithmes de tri ? En 20 secondes ?
Pour mesurer, vous pouvez utiliser time ./prog dans le terminal pour lancer le programme prog et afficher le temps de son exécution.
Répondre à la même question en utilisant des tableaux de valeurs aléatoires croissantes ou décroissantes. Expliquer le comportement du tri rapide.