Tris

• 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.

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

int values[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

int compare(const void *a,const void *b)
{
  int aint = *(int*)a;
  int bint = *(int*)b;
  if (aint == bint)
    return 0;
  else
    if (aint < bint)
      return -1;
    else
      return 1;
}

int main()
{
  int i;
  for (i=0; i < 10; i++)
    printf("%d ", values[i]);
  printf("\n");
  
  qsort (values, 10, sizeof(int), compare);
  
  for (i=0; i < 10; i++)
    printf ("%d ", values[i]);
  printf("\n");

  return 0;
}

• Effectuer un test avec un tableau de 1000 entiers aléatoires :
  1. Créer un tableau de référence.
  2. Copier la référence vers un deuxième tableau (la copie).
  3. Trier la référence avec qsort et la copie avec selection_sort.
  4. Comparer les résultats des deux algorithmes.
• Effectuer plusieurs tests ; pour des petits tableaux et pour des grands ; pour des tableaux aléatoires, triés, presque triés, inversés ; pour des tableaux avec peu de clés distinctes, etc.

• Tri par insertion (vu en cours)
• Tri rapide (quicksort, vu en cours)

• Introduire l'amélioration suivante : si la taille du tableau diminue en dessous d'un certain seuil CUTOFF, alors vous appelez insertion_sort sur ce tableau. Noter qu'il faut modifier les arguments à la fonction insertion_sort pour qu'elle puisse trier une partie d'un tableau commencant et terminant par des indices quelconques.
• Mesurer le temps d'exécution sur un tableau aléatoire de taille 10^7 pour des valeurs de CUTOFF entre 1 et 100 et choisir le meilleur seuil.
• Introduire d'autres améliorations vues au cours. Vérifier la performance sur des types de données différentes, en particulier sur des tableaux déjà triés, des tableaux inversés et des tableaux avec peu de clés distinctes (même avec 1 ou 2 clés). Rendez la version la plus rapide que vous avez obtenue.

• 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.
• Ajouter deux variables globales nb_less et nb_swap dans le fichier sort.c
• Ajouter une incrémentation nb_less++ dans la fonction less> ainsi qu'une incrémentation nb_swap++ dans la fonction swap.
• Déclarer les variables nb_less et nb_swap comme étant extern dans le fichier tp04-instr.c :

  extern int nb_less;
  extern int nb_swap;
  

• Par exemple, pour compter le nombre de comparaisons et d'échanges du tri par sélection, vous pouvez ajouter les lignes suivantes dans le fichier tp04-instr.c :

  nb_less = 0;
  nb_swap = 0;
  
  selection_sort(tab, size);
  
  printf("%d comparaisons\n", nb_less);
  printf("%d échanges\n", nb_swap);
  

  Il suffira alors de réaliser des appels aux différents tris pour avoir un comparatif du nombre de comparaisons (ou d'échanges) qu'ils nécessitent.
• Pour visualiser le nombre de comparaisons et d'échanges 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 et du tri par insertion.
    Ainsi, par exemple, une ligne contenant les entiers 10 55 37 signifie que, pour trier un tableau contenant 10 éléments, il a fallu 55 comparaisons pour le tri par sélection et 37 comparaisons pour le tri par insertion.
  • 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
    

    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 éléments (entiers) 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 faisant le lien entre les résultats de vos algorithmes et la théorie vue au cours, écrire un court rapport du tp. Le rapport doit contenir les éléments suivants avec des explications du comportement des algorithms.
  1. Un diagramme avec le nombre de comparaisons de tri par sélection, tri par insertion et quicksort sur des tableaux de taille 0, 100, 200, ..., 10 000. Les éléments des tableaux sont aléatoires.
  2. Un diagramme avec le nombre de comparaisons de tri par sélection, tri par insertion et quicksort sur des tableaux de taille 0, 10, 20, ..., 100. Les éléments des tableaux sont aléatoires.
  3. Un diagramme avec le nombre d'échanges de tri par sélection et tri par insertion sur des tableaux de taille 0, 100, 200, ..., 10 000. Les éléments des tableaux sont aléatoires.
  4. Un ou plusieurs diagrammes montrant la taille maximale d'un tableau que vous pouvez trier en 1, 2, ..., et en 20 secondes avec les trois algorithmes de tri différents. Les éléments des tableaux sont aléatoires. Pour mesurer, vous pouvez utiliser time ./votre_prog dans le terminal pour lancer le programme votre_prog et afficher le temps de son exécution.
  5. Un ou plusieurs diagrammes montrant la taille maximale d'un tableau que vous pouvez trier en 1, 2, ..., et en 20 secondes avec les trois algorithmes de tri différents. Utilisez des tableaux en ordre croissant (déjà triés) et en ordre décroissant (inversés). Comaparez avec les résultats du point précédent. Si vous avez fait l'exercice 4, vous pouvez inclure la version de base ainsi que la version améliorée de quicksort.