TP2 : Table (d’entiers)¶

table.h¶

Dans un fichier table.h, créer un type structuré Table avec trois champs :

le pointeur vers le tableau en mémoire, “data”
la taille du tableau en mémoire, “size”
le nombre d’éléments dans la table, “n”

Ajouter une constante RATIO égale à 50.

Déclarer les fonctions suivantes :

Table* new_table(int size); alloue dynamiquement une nouvelle table, initialise correctement tous les champs et renvoie son adresse ou NULL en cas de problème d’allocation ;
void free_table(Table*); libère la mémoire associée à une table allouée dynamiquement ;
void print_table(Table*); affiche les n éléments d’une table, encadrés par des [] et séparés par des , (la table est passée par adresse uniquement pour économiser une copie) ;
int is_sorted(Table*); renvoie 1 si les éléments de la table sont triés par ordre croissant, 0 sinon ;
int dicho_search(Table* t,int x); réalise une recherche dichotomique de l’élément x dans une table triée et renvoie sa position, ou -1 si l’élément n’est pas dans la table (vous pourrez utiliser pour écrire cette fonction une fonction intermédiaire dicho_rec() qui prend plus de paramètres, mais elle ne doit pas apparaitre dans le .h) ;
int insert(Table * t, int e); ajoute e dans une table triée, avec réallocation de la mémoire associée : si le nombre d'éléments présents dans le tableau (n) est supérieur à RATIO pour-cent de la taille du tableau (size), on double la taille (avec realloc). La fonction renvoie la position de l'élément ajouté ou -1 si l'ajout n'a pas été possible (erreur d'allocation mémoire) ;

Attention

Ne pas oublier de mettre à jour n et size. Bien vérifier que n est toujours plus petit ou égale à size. Le code doit fonctionner correctement si on change la valeur de RATIO pour toute valeur entre 1 et 100.

int random_inserts(Table* t, int nb); réalise l'ajout de nb valeur aléatoire dans la table, renvoie le nombre d'ajouts effectués ;

void shuffle(Table* t); mélange le tableau aléatoirement ;

procédure shuffle(tableau T)
  pour i de 0 à taille(T)-1
    # tirer un nombre aléatoire entre 0 et taille(T)
        r ← random(0,taille(T))
        # échanger les valeurs aux positions i et r
        swap(T[i], T[r])

int del(Table * t, int e); enlève e dans une table triée, avec réallocation de la mémoire associée à la table si l'occupation de la table est inférieur à RATIO/2 pour-cent (la nouvelle taille devra être l'ancienne divisée par deux si possible, sinon égale exactement au nombre d'éléments), renvoie l'ancienne position de l'élément e ou -1 si deletion impossible (élément non présent) ;

Attention

Bien vérifier que size est toujours supérieur ou égal à 1 et que n est toujours inférieur ou égal à size

BONUS int del_mutiple(Table * t, int e); enlève toutes les occurrences de e dans d'une table, renvoie le nombre de délétions effectuées ;
BONUS int clean(Table * t); enlève tous les doublons dans une table, renvoie le nombre de délétions effectuées ;

void insertion_sort(Table* t); réalise le tri par insertion de la table t ;

procédure tri_insertion(tableau T)
  pour i de 1 à taille(T) - 1
    # mémoriser T[i] dans x
    x ← T[i]                            
    # décaler les éléments T[0]..T[i-1] qui sont plus grands que x, en partant de T[i-1]
    j ← i                               
    tant que j > 0 et T[j - 1] > x
      T[j] ← T[j - 1]
      j ← j - 1
    # placer x dans le "trou" laissé par le décalage
    T[j] ← x

void quick_sort(Table* t, int(*pivot)(Table*,int,int)); réalise le tri quicksort en prenant comme fonction de choix de pivot la fonction passée en paramètre ;

partitionner(tableau T, entier premier, entier dernier, entier pivot)
  échanger T[pivot] et T[premier]  # échange le pivot avec le premier du tableau , le pivot devient le premier du tableau
  pivot ← premier
  Tant que premier < dernier
    Tant que T[premier] <= T[pivot] ET premier < Taille(T)
        premier ← premier + 1
    Tant que T[dernier] >= T[pivot] ET dernier > pivot
      dernier ← dernier - 1
    si premier < dernier alors
      échanger T[premier] et T[dernier]
  échanger T[dernier] et T[pivot]
  renvoyer dernier

tri_rapide(tableau T, entier premier, entier dernier)
        si premier < dernier alors
            pivot ← choix_pivot(T, premier, dernier)
            pivot ← partitionner(T, premier, dernier, pivot)
            tri_rapide(T, premier, pivot-1)
            tri_rapide(T, pivot+1, dernier)

int pivot_first(Table*, int b, int e); renvoie b ;
int pivot_middle(Table*, int b, int e); renvoie l'indice du milieu du sous tableau considéré, c'est à dire (e-b)/2+b;
int pivot_random(Table*, int b, int e); renvoie un entier aléatoire entre b et e:w.

table.c et test.c¶

Dans un fichier table.c, écrivez le code des fonctions et dans un fichier test.c écrivez une fonction main() permettant de tester. Vous compilerez à l'aide de l'utilitaire make (il faut donc écrire un fichier Makefile).

Comptage¶

Ajoutez une constante DEBUG et du code dans chacune de vos fonctions : si DEBUG vaut 1, vos fonctions comptent le nombre d'opérations effectués (les échanges) et l'affiche avant de terminer. Sinon rien ne change.

Comparez les valeurs en faisant varier la taille de votre table pour les différents algorithmes de tris et choix de pivot. Pour chaque cas faire plusieurs tirages aléatoires afin d'avoir une valeur représentative statistiquement.

Votre code constitue une boite à outils. On vous demande ici d'utiliser votre boite à outils pour faire une analyse pertinente de la complexité des algorithmes implémentés.

Idées : sur le même graphique, tracer une courbe pour chaque algorithme représentant la variation du nombre moyen (par exemple sur 10 expériences) de permutations effectuées en fonction de la taille du tableau. Commenter les courbes et conclure.

Le code et le rapport sont à rendre sur blackboard.