Exercice langage C tassage et fusion de suites ordonnées

Exercice 1:

[1] Première solution (juste mais onéreuse) :

#include 

#define N 20

int i, j, n,
                                                /* pour la mise au point */
    t[N] = { 1, 2, 0, 3, 0, 0, 4, 5, 0, 6, 0, 7, 0, 0, 8, 9, 0, 0, 0, 10 };

main(void) {
    n = N;

    i = 0;
    while (i < n)
        if (t[i] == 0) {
            for (j = i + 1; j < n; j++)
                t[j - 1] = t[j];
            n--;
        } else
            i++;

    for (i = 0; i < n; i++)
        printf("%d ", t[i]);
    printf("\n");
}

C’est sans doute la première idée qui vient à l’esprit : parcourir le tableau (i représente ce parcours) et lorsque t[i] est nul : avancer d’une position tous les éléments entre t[i+1] et t[n - 1], decrémenter n et ne pas incrémenter i, car l’élément qui était à la position i+1 et qui est maintenant à la position i est peut-être nul lui aussi.

[2] Cela est juste mais pas très efficace : une boucle imbriquée dans une autre, cela implique souvent des opérations répétées de l’ordre de n² fois. [ Par exemple, ici, si on suppose qu’un élément sur deux est nul, l’opérationt[j - 1] = t[j] sera exécutée n-2 fois, puis n-4 fois, ensuite n-6 fois, etc. et, au total, un nombre de fois proche de la moitié de la somme des n-2 premiers entiers. Soit (n-2)(n-1)/4, c’est bien de l’ordre de n². ]

Pourquoi ne pas faire un seul parcours du tableau, en plaçant chaque élément non nul directement à sa place finale ? Le programme obtenu est d’un coût linéaire, c’est à dire de l’ordre de n obtenu (En fait, la bonne question est : pourquoi on n’a pas eu cette idée en premier ?) :

#include 

#define N 20

int i, j, n,
                                                /* pour la mise au point */
    t[N] = { 1, 2, 0, 3, 0, 0, 4, 5, 0, 6, 0, 7, 0, 0, 8, 9, 0, 0, 0, 10 };

main(void) {
    n = N;

    j = 0;
    for (i = 0; i < n; i++)
        if (t[i] != 0)
            t[j++] = t[i];
    n = j;

    for (i = 0; i < n; i++)
        printf("%d ", t[i]);
    printf("\n");
}

Exercice 2:

#include 

#define NA 12
#define NB  8

int c[NA + NB], ia, ib, ic, i,
                                        /* pour la mise au point */
    a[NA] = {  1,  3,  4,  8,  9, 11, 12, 14, 17, 18, 19, 20},
    b[NB] = {  2,  5,  6,  7, 10, 13, 15, 16 };

main(void) {
    ia = 0;
    ib = 0; 
    ic = 0;

    while (ia < NA && ib < NB)
        if (a[ia] <= b[ib])
            c[ic++] = a[ia++];
        else
            c[ic++] = b[ib++];

    while (ia < NA)
        c[ic++] = a[ia++];

    while (ib < NB)
        c[ic++] = b[ib++];

    for (i = 0; i < ic; i++)
        printf("%d ", c[i]);
    printf("\n");

    system("pause");
}

Il s’agit de l’algorithme classique de la fusion de deux suites triées : tant qu’il reste des éléments à examiner dans l’un et l’autre tableau, on compare l’élément du premier tableau dont c’est le tour avec celui du second tableau dont c’est le tour également, et on fait passer le plus petit des deux dans le tableau résultat. Quand un des deux tableaux est épuisé il faut recopier ce qui reste dans l’autre tableau.

Observez que les deux tableaux donnés doivent être triés, et que le tableau résultat est alors trié.

Le sujet n’en dit rien, mais s’il avait fallu réduire les doublons alors il aurait fallu écrire la partie centrale comme ceci :

    ...
    while (ia < NA && ib < NB)
        if (a[ia] = b[ib]) {
            c[ic++] = a[ia++];
	        ib++;
        } else if (a[ia] < b[ib])
            c[ic++] = a[ia++];
        else
            c[ic++] = b[ib++];
    ...