:: Enseignements :: ESIPE :: E3INFO :: 2015-2016 :: 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 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 array.h et array.c contiennent des fonctions de base sur les tableaux, les fichiers sort.h et sort.c des fonctions de tri et le fichier tp04.c contient une fonction main qui va nous permettre de tester les tris. Les fichiers visualarray.h, visualarray.c, demo1.c et demo2.c contiennent des fonctions pour visualiser l'exécution d'un algorithme de tri. Le fichier Makefile permet de générer un exécutable de nom ./tp04.

Tester par make que cela fonctionne et exécuter ./tp04 pour constater que la fonction selection_sort() appelée dans tp04.c à la ligne 34 ne fonctionne pas correctement.
Aller voir dans sort.c et faire ce qu'il faut pour que le tri sélection soit correctement réalisé. Tester à nouveau l'exécution après avoir relancé le Makefile.
Dans tp04.c, changer la valeur de MAX_SIZE en début de fichier. Par exemple, essayer avec 0: est-ce que votre fonction de tri fonctionne correctement? Essayer maintenant avec 1000: est-ce que votre fonction de tri fonctionne correctement?
L'archive contient aussi des fonctions pour faciliter la visualisation de tableaux. Taper make demo1 et exécuter ./demo1 ou taper make demo2 et exécuter ./demo2 pour voir des exemples pour un tri à bulles simple. Vous pouvez vous inspirer de ces deux exemples pour visualiser vos propres algorithmes dans ce tp.

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 selection_sort 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 array.h et implémentez-les dans array.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 have_same_content_array(int t1[], int t2[], int size) 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 sort.c de nos tris dont les prototypes de fonction sont décrits dans le fichier sort.h.

Tri par insertion (vu en cours)
Tri à bulles (vu en cours)
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.

Recopier chacune des fonctions de tri dans sort.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. Noter qu'un échange de deux valeurs dans un tableau s'effectue par 3 déplacements.
Par exemple:
```
void selection_sort(int tab[], int size);
void selection_sort_instr(int tab[], int size, int *nb_comp, int *nb_assign);
```
Sur la base des fonctions de tri réalisées précédemment, implémenter dans sort.c les versions instrumentées de chacune d'entre elle.

Vous pouvez alors créer un 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 <time.h>

#include "array.h"
#include "sort.h"

#define MAX_VALUE 1000000
#define MAX_SIZE 1000

int main(int argc, char *argv[]) {
  srand(time(NULL));
  int size = MAX_SIZE;
  int max_value = MAX_VALUE;
  /* tableau de référence */
  int* tab_ref = NULL;
  /* tableau de travail */
  int* tab = NULL;
  /* compteurs */
  int nb_comp = 0;
  int nb_assign = 0;

  /* allocation et initialisation de la référence avec des valeurs aléatoires */
  tab_ref = create_array(size);
  fill_random_array(tab_ref, size, max_value);
  /* allocation et initialisation du tableau de travail avec les valeurs de référence */
  tab = create_array(size);
  copy_array(tab_ref, tab, size);
  /* tri du tableau de travail */
  selection_sort_instr(tab, size, &nb_comp, &nb_assign);
  printf("%d comparaisons\n", nb_comp);
  printf("%d déplacements\n", nb_assign);
  /* 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 sort.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 "sort.ps"
set terminal postscript color "landscape"
set title "nombre de comparaisons"

plot \
"sort.dat" using 1:2 title "tri par selection" with lines linetype 1, \
"sort.dat" using 1:3 title "tri par insertion" with lines linetype 2, \
"sort.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 sort.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 sort.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 sort.ps ou evince sort.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.
Écrire un court rapport du tp contenant les éléments suivants :
1. Un diagramme avec le nombre de comparaisons de tri par sélection, tri par insertion et tri rapide sur des tableaux de taille 10 à 10 000 avec une valeur maximale d'au moins 20 000. Commenter le résultat en quelques phrases.
2. Un diagramme avec le nombre de comparaisons de tri par sélection, tri par insertion et tri rapide sur des tableaux de taille 10 à 100 avec une valeur maximale d'au moins 200. Commenter le résultat en quelques phrases.
3. Un diagramme avec le nombre de comparaisons de tri par sélection, tri par insertion et tri à bulles sur des tableaux de taille 10 à 10 000 avec une valeur maximale d'au moins 20 000. Commenter le résultat en quelques phrases.
4. Un diagramme avec le nombre de déplacements de tri par sélection, tri par insertion et tri à bulles sur des tableaux de taille 10 à 10 000 avec une valeur maximale d'au moins 20 000. Commenter le résultat en quelques phrases.
5. Pour chaque algorithme de tri différent, le nombre d'entiers que vous pouvez trier en 10 secondes et en 20 secondes. Pour mesurer, vous pouvez utiliser time ./un_prog dans le terminal pour lancer le programme un_prog et afficher le temps de son exécution.