Compter le nombre de comparaisons dans un tri insertion

Résolu
Theo_0055 Messages postés 275 Date d'inscription   Statut Membre Dernière intervention   -  
Theo_0055 Messages postés 275 Date d'inscription   Statut Membre Dernière intervention   - 22 sept. 2022 à 20:21

Bonjour,

On me demande d'écrire en C une fonction de tri par insertion. De plus, il faut que ma fonction renvoie le nombre de comparaisons effectués entre chaque élément du tableau T de taille n.

J'ai réussi à écrire la fonction et je l'ai testée. Elle marche mais ne retourne pas le bon nombre de comparaisons.

Je vous explique ce que j'ai en tête pour que vous puissiez comprendre.

Exemple 1 : Si T = [4, 1, 3, 2], on a besoin de faire 6 comparaisons :

  • On compare 1 avec 4
  • On compare 3 avec 4
  • On compare 3 avec 1
  • On compare 2 avec 4
  • On compare 2 avec 3
  • On compare 2 avec 1

Exemple 2 : Si T = [1, 2, 3, 9, 8], on a besoin de faire 10 comparaisons :

  • On compare 2 avec 1
  • On compare 3 avec 2
  • On compare 3 avec 1
  • On compare 9 avec 3
  • On compare 9 avec 2
  • On compare 9 avec 1
  • On compare 8 avec 9
  • On compare 8 avec 3
  • On compare 8 avec 2
  • On compare 8 avec 1

J'ai remarqué que :

  • pour l'élément à la position i = 0 on a effectue 1 comparaison
  • pour l'élément à la position i = 1 on a effectue 2 comparaisons
  • pour l'élément à la position i = 2 on a effectue 3 comparaisons
  • etc.

On a donc chaque fois i-1 comparaisons.

J'ai essayé de faire ceci avec le deuxième exemple, mais ma fonction me retourne 11 au lieu de 10.

#include <stdio.h>

int tri_insertion(int t[], int n) {
  int i, j;
  int clef, nb_comparaison = 0;

  for (i = 1; i < n; i++) {
    clef = t[i];
    j = i - 1;
   
    /* Décalage des valeurs du tableau */
    while ((j >= 0) && (t[j] > clef)) {
      t[j + 1] = t[j];
      j = j - 1;
      nb_comparaison += 1;
    }
    nb_comparaison += 1;
    /* insertion de la clef */
    t[j + 1] = clef;
  }
  return nb_comparaison;
}

void afficher(int tab[], int n){
  int i;    
  printf("[");
  for (i = 0; i < n; i++) {
    /* Affichage de chaque élément de tableau */
    printf("%d ", tab[i]);
  }
  printf("]\n");
}

int main() {
   int tab[6] = {1, 2, 3, 9, 8};
   int n = tri_insertion(tab, 6);
   printf("%d\n", n);
 
   // afficher(tab, 6);
   return 0;
}


Windows / Chrome 105.0.0.0

A voir également:

7 réponses

[Dal] Messages postés 6204 Date d'inscription   Statut Contributeur Dernière intervention   1 104
 

Salut,

Je n'ai pas étudié ton implémentation en détails, mais dans :

while((j >= 0) && (t[j] > Clef)) {

Tu fais 2 comparaisons. Le while ne fera pas la comparaison (t[j] > Clef) si la première comparaison (j >= 0) est évaluée à faux, car les deux conditions sont cumulatives et il suffit que la première soit fausse pour que le compilateur passe à la suite.

Or, tu comptes ce cas comme une comparaison du contenu du tableau en incrémentant ton compteur en sortie de boucle, alors que while a seulement évalué (j >= 0).

Dal

0
Theo_0055 Messages postés 275 Date d'inscription   Statut Membre Dernière intervention   1
 

J'ai essayé de déplacer cela en sortie de boucle, mais le résultat est toujours faux.

0
Theo_0055 Messages postés 275 Date d'inscription   Statut Membre Dernière intervention   1
 
#include <stdio.h>

int tri_insertion(int t[], int n) {
  int i, j;
  int clef, nb_comparaison = 0;

  for(i = 1; i < n; i++) {
    clef = t[i];
    j = i - 1;
   
    /* Decalage des valeurs du tableau */
    while ((j >= 0) && (t[j] > clef)) {
      t[j + 1] = t[j];
      j = j - 1;
      nb_comparaison+=1;
    }
    nb_comparaison+=1;
    /* insertion de la clef */
    t[j + 1] = clef;
  }
  return nb_comparaison - 1;
}

void afficher(int tab[],int n) {
  int i;    
  printf("[");
  for (i = 0; i < n; i++) {
    /* Affichage de chaque élément de tableau */
    printf("%d ", tab[i]);
  }
  printf("]\n");
}

int main() {
    int tab[11]={6, 9, 47, 90, 87, 1, 23, 65, 0, 5, 99};
    int n = tri_insertion(tab, 11);
    printf("%d", n);
 
    // afficher(tab, 6);
    return 0;
    
}

J'ai changé ma fonction en faisant a la sortie nb_comparaison -1

Pour l'exemple précédent ca me donne 10(bon résultat)

Mais il faut que je la teste sur d'autres exemples pour voir si c'est fiable ce que j'ai écrit et là je trouve 35 esce correct?

0
[Dal] Messages postés 6204 Date d'inscription   Statut Contributeur Dernière intervention   1 104
 

Pour n'incrémenter le compteur que lorsque tu fais la comparaison dans le 2ème test de ton while, il te suffit ... d'incrémeter exactement à cet endroit, et tu n'as pas d'autres additions ou soustractions à faire dans ta fonction sur ta variable nb_comparaison.

    /* Decalage des valeurs du tableau */
    while((j >= 0) && (nb_comparaison+=1, t[j] > Clef)) {
      t[j+1] = t[j];
      j = j - 1;
    }

0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Theo_0055 Messages postés 275 Date d'inscription   Statut Membre Dernière intervention   1
 

Lorsque je mets ça dans mon code ça me renvoie toujours 11.

On est bien d'accord que le nombre de comparaison pour T=[4,1,3,2] est bien égal à 10 ?

0
[Dal] Messages postés 6204 Date d'inscription   Statut Contributeur Dernière intervention   1 104
 

Chez moi ce tableau donne 6 comparaisons.

En ce qui me concerne, j'aime bien automatiser mes tests. On peut utiliser assert() pour effectuer des tests unitaires rudimentaires.

Voilà un exemple qui permet, non seulement, de vérifier que le tableau trié attendu est bien produit, outre le résultat renvoyé de nombre de comparaisons.

#include <stdio.h>
#include <assert.h>

int tri_insertion(int t[], int n) {
        int i,j;
        int Clef,nb_comparaison=0;

        for(i=1; i < n; i++) {
                Clef = t[i];
                j = i - 1;
                /* Decalage des valeurs du tableau */
                while((j >= 0) && (nb_comparaison+=1, t[j] > Clef)) {
                        t[j+1] = t[j];
                        j = j - 1;
                }
                /* insertion de la clef */
                t[j+1] = Clef;
        }
        return nb_comparaison;
}

int is_arr_eq(int t1[], int t2[], size_t n) {
        for (size_t i = 0; i < n; i++)
                if (t1[i] != t2[i])
                        return 0;
        return 1;
}

int main(void) {
        {
                size_t n = 1;
                int input_arr[]    = { 1 };
                int expected_arr[] = { 1 };
                tri_insertion(input_arr, n);
                assert(is_arr_eq(input_arr, expected_arr, n));
        }
        {
                size_t n = 2;
                int input_arr[]    = { 1, 2 };
                int expected_arr[] = { 1, 2 };
                tri_insertion(input_arr, n);
                assert(is_arr_eq(input_arr, expected_arr, n));
        }
        {
                size_t n = 2;
                int input_arr[]    = { 2, 1 };
                int expected_arr[] = { 1, 2 };
                tri_insertion(input_arr, n);
                assert(is_arr_eq(input_arr, expected_arr, n));
        }
        {
                size_t n = 3;
                int input_arr[]    = { 2, 3, 1 };
                int expected_arr[] = { 1, 2, 3 };
                tri_insertion(input_arr, n);
                assert(is_arr_eq(input_arr, expected_arr, n));
        }
        {
                size_t n = 4;
                int input_arr[]    = { 4, 1, 3, 2 };
                int expected_arr[] = { 1, 2, 3, 4 };
                assert(tri_insertion(input_arr, n) == 6);
                assert(is_arr_eq(input_arr, expected_arr, n));
        }
        {
                size_t n = 5;
                int input_arr[]    = { 4, 5, 1, 3, 2 };
                int expected_arr[] = { 1, 2, 3, 4, 5 };
                assert(tri_insertion(input_arr, n) == 10);
                assert(is_arr_eq(input_arr, expected_arr, n));
        }
        printf("Tous les tests ont été exécutés sans erreurs\n");

        return 0;
}

Les instructions assert() vérifient que le contenu de la parenthèse est évalué à "vrai". Si ce n'est pas le cas, le programme s'arrête en produisant une erreur indiquant la ligne du test qui échoue (s'il y en a une).

Le code ci-dessus passe les différents tests et donne, en l'état :

$ gcc -Wall -Wextra 37691488.c
$ ./a.out 
Tous les tests ont été exécutés sans erreurs

Tu devrais aussi vérifier quel nombre de comparaisons ton programme doit donner dans autres cas de tableaux plus simples avec un tableau à 1 élément, un tableau à 2 éléments déjà trié et un autre non trié, etc. et rajouter les assertions manquantes dans le code ci-dessus en ligne 34, 41, 48 et 55, et dans d'autres cas que tu voudrais ajouter.

Le cas d'un "tableau vide" (ou en tout cas un paramètre de taille n valant 0) pourrait aussi être testé, si tu décides qu'il est de la responsabilité de ta fonction de vérifier que la taille passée n'est pas vide et décider quoi faire dans ce cas (message d'erreur, etc.), ou alors, tu spécifies dans la documentation de ta fonction que la taille passée ne peut être vide et qu'il est de la responsabilité de l'appelant de le vérifier, ce qui est une façon valable de traiter ce cas (ou plutôt de t'en décharger), dès lors que tu documentes le fonctionnement de ta fonction.

0
Theo_0055 Messages postés 275 Date d'inscription   Statut Membre Dernière intervention   1
 

Ah je savais pas que en C il y avit des assert,cool c'est comme en Python .

Ah vous avez anticipé on m'a aussi demandé de le faire pour différents taille de tableau

Je comprends ce que vous vouliez dire merci en gros c'est la spécifiction de la fonction

0
[Dal] Messages postés 6204 Date d'inscription   Statut Contributeur Dernière intervention   1 104
 

En fait, tu peux même écrire tes tests avant de coder ta fonction :-)

C'est une méthode de développement : https://fr.wikipedia.org/wiki/Test_driven_development

Automatise tes tests et conçois tes programmes de façon à ce que tu puisses les tester automatiquement, et exécute l'intégralité de tes tests à chaque modification, pour vérifier l'absence de régression. Que tu fasses du TDD ou pas, cela te rendra service.

Lorsque tu écris tes tests, écris les pour tester les comportements attendus par ton programme (spécifications), pas les détails de l'implémentation, qui pourront changer à mesure de l'avancement de ton travail.

0
Theo_0055 Messages postés 275 Date d'inscription   Statut Membre Dernière intervention   1
 

Merci beaucoup 

le reste de mon exo je vais essayer de faire seul et j'espere que j'y arriverais

merci

0