Cliquer ici pour imprimer

Dernière modification : 08/11/2022 à 08:38

TP2 - Tableaux et tris
TP2 - Tableaux et tris

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 à la table si nécessaire (on choisira alors une nouvelle taille pour que le taux d’occupation soit égal à RATIO), renvoie la position de l’élément ajouté ou -1 si l’ajout n’a pas été possible (erreur d’allocation mémoire) ;
  • 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])
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 pourcent (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) ;
  • BONUS int del_mutiple(Table * t, int e); enlève toutes les occurances 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   
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)
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); renvoit b ;
  • int pivot_middle(Table*, int b, int e); renvoit l’indice du milieu du sous tableau considéré, c’est à dire (e-b)/2+b;
  • int pivot_random(Table*, int b, int e); renvoit 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 et l’affiche avant de terminer. Sinon rien ne change.

Comparez les valeurs en faisant varier la taille de votre table.