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 :

Ajouter une constante RATIO égale à 50.

Déclarer les fonctions suivantes :

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])
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   
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)

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.