Exercices (pc2)

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

a = 3 2 5 1 4
inv = 0 1 2 0 2

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

3 2 5 1 4 1 3 2 5 4 1 2 3 4 5  0 1 2 0 2 0 0 1 0 1 0 0 0 0 0

2. Donner l’algorithme de calcul de inv à partir de a.

3. Donner le calcul de a à partir de inv.