Aller au contenu

Colle 2 — Fusion et tri par comptage

Colle · MP2I · exercices 1 et 2 de la colle 2

Cours : Tri fusion · Complexité

Autres parties : Exercice 3. Arbres dans des tableaux

Les fonctions sont à écrire en C. Chaque question est suivie de tests qui doivent passer sans erreur.

Exercice 1 — Fusion de tableaux triés

On souhaite ici écrire une fonction fusion qui permet, étant donné deux tableaux triés t1 et t2, de construire un tableau tf contenant les éléments de t1 et de t2 mais globalement triés.

Ainsi, si t1 contient 0, 1, 4, 6 et t2 contient 1, 2, 3, 4, 5, le tableau tf contiendra 0, 1, 1, 2, 3, 4, 4, 5, 6.

Question 1

Écrire la fonction fusion.

void fusion(int t1[], int n1, int t2[], int n2, int tf[])
{
    // t1 contient n1 éléments, t2 contient n2 éléments
    // et tf contient n1+n2 éléments indéterminés
}
Corrigé 
void fusion(int t1[], int n1, int t2[], int n2, int tf[])
{
    int a = 0;
    int b = 0;
    for(int i = 0; i < n1 + n2; i++)
    {
        if (a < n1 && (b == n2 || t1[a] < t2[b]))
        {
            tf[i] = t1[a];
            a++;
        }
        else
        {
            tf[i] = t2[b];
            b++;
        }
    }
}

Tests :

int t1[] = { 0, 1, 4, 6 };
int t2[] = { 1, 2, 3, 4, 5 };
int t[9];
fusion(t1, 4, t2, 5, t);
int tres[] = {0, 1, 1, 2, 3, 4, 4, 5, 6};
assert(memcmp(t, tres, sizeof(int) * 9) == 0);

Question 2

Prouver la correction de la fonction précédente. Il faudra non seulement s'assurer que le tableau final est trié, mais aussi qu'il contient exactement les éléments de t1 et de t2.

Corrigé

On va noter ici \(N = n_1+n_2\) et \(t[i..j]\) les éléments de \(t\) aux indices entre \(i\) et \(j\). On note aussi \(t1[n_1] = t2[n_2] = +\infty\).

On va prouver l'invariant

\[ I(i,a,b) = \mathrm{trie}(i) \wedge \mathrm{min12}(i,a,b) \wedge \mathrm{memes}(i,a,b) \wedge i = a + b \wedge a \le n_1 \wedge b \le n_2 \]

où \(\mathrm{trie}(i)\) signifie que \(tf[0..i-1]\) est trié, \(\mathrm{min12}(i,a,b)\) signifie que \(\forall k < i,\ tf[k] \le \min(t1[a],t2[b])\) et \(\mathrm{memes}(i,a,b)\) que \(tf[0..i-1]\) contient exactement les mêmes éléments que \(t1[0..a-1]\) et \(t2[0..b-1]\) réunis.

  • Initialisation : au départ \(i=a=b=0\) et on a donc directement \(\mathrm{trie}(0)\), \(\mathrm{min12}(0,0,0)\) et \(\mathrm{memes}(0,0,0)\) car tout est vide.
  • Hérédité : supposons \(I(i,a,b)\) vérifié au début de l'itération, avec \(i < N\). Alors :
    • Soit on est dans le premier cas car \(a < n_1\), \(b < n_2\) et \(t1[a] < t2[b]\). On va alors affecter \(t1[a]\) à \(tf[i]\), or \(\mathrm{min12}(i,a,b)\) est vérifié, donc pour \(k < i\) on a \(tf[k] \le \min(t1[a],t2[b]) = t1[a] = tf[i]\). Ainsi \(\mathrm{trie}(i+1)\) est vérifié. De plus, \(tf[i] = t1[a] \le t1[a+1]\) car \(t1\) est trié (ou \(t1[a+1] = +\infty\) si \(a+1 = n_1\)) et \(tf[i] < t2[b]\) par hypothèse. Donc on a \(\mathrm{min12}(i+1,a+1,b)\) vérifié. \(\mathrm{memes}(i+1,a+1,b)\) est vérifié directement car on a juste \(t1[a]\) comme nouvel élément et c'est celui qu'on a rajouté. Enfin, \(i+1 = (a+1) + b\) vu que \(i = a+b\), et \(a + 1 \le n_1\).
    • Soit on est dans le premier cas car \(a < n_1\) et \(b = n_2\). Il suffit de reprendre le cas précédent en ayant en tête qu'on a posé \(t2[b] = +\infty\).
    • Soit on est dans le second cas. Alors \(b < n_2\) : sinon, on aurait \(b = n_2\) et donc \(a = i - n_2 < n_1\), et on serait dans le premier cas. On a donc \(a = n_1\) ou \(t2[b] \le t1[a]\), c'est-à-dire, avec la convention \(t1[n_1] = +\infty\), \(t2[b] \le t1[a]\) dans tous les cas. Ce cas est alors symétrique des précédents en échangeant les rôles de \(t1\) et \(t2\) (et donc de \(a\) et de \(b\)).

L'invariant est bien vérifié en sortie d'itération.

Conclusion : on a \(I(N,a,b)\) en sortie, avec \(N = a+b\), \(a \le n_1\) et \(b \le n_2\). Comme \(N = n_1 + n_2\), forcément \(a = n_1\) et \(b = n_2\). Ainsi \(tf\) est trié et il contient les mêmes éléments que \(t1\) et \(t2\).

Question 3

Déterminer la complexité de cette fonction.

Corrigé

Pas de difficulté ici, on a une boucle for qui effectue un nombre constant d'opérations élémentaires lors de chacune de ses \(N\) étapes. On est donc en \(O(N) = O(n_1+n_2)\).

Exercice 2 — Tri par comptage

On considère ici une méthode de tri dite par comptage. On va supposer que les tableaux qu'on cherche à trier ne contiennent que des entiers entre \(0\) et \(N-1\) où \(N\) est fixé. L'idée est alors, dans un tableau de taille \(N\), de compter le nombre d'occurrences de chacun des entiers. Ensuite, on peut se servir de ce tableau d'occurrences pour en déduire le tableau trié.

On demande à ce que la complexité soit en \(O(N+n) = O(n)\) en supposant \(N\) constant, où \(n\) est la taille du tableau à trier.

Question 4

Écrire la fonction occurrences.

void occurrences(int t[], int n, int occ[], int N)
{
    // t est un tableau de n entiers
    // occ est un tableau de N entiers dont les valeurs sont
    // non initialisées.
    // on demande de placer dans occ[i] le nombre d'occurrences de i dans t
}
Corrigé 
void occurrences(int t[], int n, int occ[], int N)
{
    for(int i = 0; i < N; i++)
        occ[i] = 0;
    for(int i = 0; i < n; i++)
        occ[t[i]]++;
}

Tests :

int t[] = { 0, 1, 2, 3, 0, 1, 2, 1 };
int occ[4];
occurrences(t, 8, occ, 4);
int res[] = { 2, 3, 2, 1 };
assert(memcmp(occ, res, sizeof(int) * 4) == 0);

Question 5

Écrire la fonction comptage.

#define N 100 // on définit ici une constante N qui vaut 100,
              // ce qui permet de faire un tableau t[N]

void comptage(int t[], int n)
{
    // t contient n entiers entre 0 et N-1
    // trier t par comptage
}
Corrigé 
void comptage(int t[], int n)
{
    int occ[N];
    occurrences(t, n, occ, N);
    int a = 0;
    for(int i = 0; i < N; i++)
    {
        for(int k = 0; k < occ[i]; k++)
        {
            t[a] = i;
            a++;
        }
    }
}

Tests :

int t[] = { 0, 1, 2, 3, 0, 1, 2, 1 };
comptage(t, 8);
int res[] = { 0, 0, 1, 1, 1, 2, 2, 3 };
assert(memcmp(t, res, sizeof(int) * 8) == 0);

Question 6

Quelle est la complexité de ce tri ? Que pensez-vous de sa pertinence si on avait fixé \(2^{31}\) comme valeur de \(N\) ?

Corrigé

Le calcul du tableau des occurrences est en \(O(N+n) = O(n)\) en supposant \(N\) constant. Le tri lui-même crée ce tableau puis effectue une boucle en \(O(N+n)\) : \(N\) pour le premier for (rien que pour gérer les indices) et \(n\) pour la somme de toutes les itérations du second for. Donc le tri est globalement en \(O(N+n) =O(n)\).

Avec une très grande valeur de \(N\), il n'est plus pertinent de considérer \(N\) constant car \(n\) est sûrement d'un ordre de grandeur plus petit. En fait, \(N\) ne doit pas être d'un ordre de grandeur plus grand que \(n\) pour que ce tri soit efficace. De plus, pour une grande valeur de \(N\), le compromis espace-temps est peu favorable : on ne va pas allouer 8 Go (\(2^{31}\) entiers de 4 octets) pour trier un tableau !

Ce tri est donc bien plus adapté pour des petites valeurs de \(N\). Il reste alors très efficace et souvent plus pertinent qu'un tri en \(O(n \log n)\) comme le tri fusion.