Tris

#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;
}

• le nombre de comparaisons (appels à less),
• le nombre d'échanges (appels à swap)

void selection_sort(int t[], int size);
void selection_sort_instr(int t[], int size, int *nb_comp, int *nb_swap);

#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_swap = 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_swap);
  printf("%d comparaisons\n", nb_comp);
  printf("%d échanges\n", nb_swap);
  /* libération des tableaux de la taille courante */
  free(tab);
  tab = NULL;
  free(tab_ref);
  tab_ref = NULL;

  return EXIT_SUCCESS;
}

• 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 valeurs, 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...).

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 d'échanges de tri par sélection et tri par insertion 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. 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.