Compter le nombre de comparaisons dans un tri insertion

Résolu/Fermé
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 - Modifié le 23 sept. 2022 à 10:16
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 - 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 6118 Date d'inscription mercredi 15 septembre 2004 Statut Contributeur Dernière intervention 22 septembre 2023 1 064
Modifié le 22 sept. 2022 à 10:52

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 mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
Modifié le 23 sept. 2022 à 10:20

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 mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
Modifié le 23 sept. 2022 à 10:22
#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 6118 Date d'inscription mercredi 15 septembre 2004 Statut Contributeur Dernière intervention 22 septembre 2023 1 064
Modifié le 22 sept. 2022 à 14:18

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 mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
Modifié le 23 sept. 2022 à 10:22

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 6118 Date d'inscription mercredi 15 septembre 2004 Statut Contributeur Dernière intervention 22 septembre 2023 1 064
Modifié le 22 sept. 2022 à 15:04

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 mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
22 sept. 2022 à 15:03

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 6118 Date d'inscription mercredi 15 septembre 2004 Statut Contributeur Dernière intervention 22 septembre 2023 1 064
Modifié le 22 sept. 2022 à 18:58

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 mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
22 sept. 2022 à 20:21

Merci beaucoup 

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

merci

0