Exercices (pc2)

La table des inversions d'une permutation est définie par: inv[i]= le nombre d'éléments < i à droite de i. On a par exemple

1. Montrer que chaque passe du tri de la bulle sur le tableau a diminue chaque élément non-nul de inv d'une unité.

   Ainsi, on aura

2. Donner l'algorithme de calcul de inv à partir de a.
3. Donner le calcul de a à partir de inv.

• About this document ...