Compter le nombre de comparaisons dans un tri insertion

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.

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.