Inversions dans un tableau⚓︎
On considère dans cet exercice des tableaux d'entiers.
Soit tab
un tel tableau. On appelle inversion un couple d'indices distincts i
et j
tel que :
i
est plus petit quej
;tab[i]
est strictement plus grand quetab[j]
.
Considérons par exemple dans le tableau :
# indices 0 1 2 3
tab = [7, 5, 9, 6]
Ce tableau compte 3 inversions :
- pour les indices
0
et1
, cartab[0]
(qui vaut7
) est strictement supérieur àtab[1]
(qui vaut5
), - pour les indices
0
et3
, cartab[0]
(qui vaut7
) est strictement supérieur àtab[3]
(qui vaut6
), - pour les indices
2
et3
, cartab[2]
(qui vaut9
) est strictement supérieur àtab[3]
(qui vaut6
).
Remarque
Compter les inversions dans un tableau permet de mesurer son « désordre » : si un tableau ne comporte aucune inversion, il est trié dans l'ordre croissant !
On demande d'écrire la fonction inversions
qui prend en argument un tableau d'entiers et renvoie son nombre d'inversions.
On convient qu'un tableau vide ne compte aucune inversion.
Les tableaux utilisés dans les tests seront de petite taille (100 éléments au maximum).
Exemples
>>> inversions([])
0
>>> inversions([5, 6, 7, 9])
0
>>> inversions([7, 5, 9, 6])
3
def inversions(tableau):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert inversions([]) == 0bksl-nlassert inversions([5, 6, 7, 9]) == 0bksl-nlassert inversions([7, 5, 9, 6]) == 3bksl-nldef inversions(tableau):bksl-nl total = 0bksl-nl taille = len(tableau)bksl-nl for i in range(taille - 1):bksl-nl for j in range(i + 1, taille):bksl-nl if tableau[i] > tableau[j]:bksl-nl total += 1bksl-nlbksl-nl return totalbksl-nlbksl-nlbksl-nl# Testsbksl-nlassert inversions([]) == 0bksl-nlassert inversions([5, 6, 7, 9]) == 0bksl-nlassert inversions([7, 5, 9, 6]) == 3bksl-nl
A
On utilise une double boucle : on compare chaque élément d'indice i
avec tous les éléments suivants d'indice j
. Si tab[j]
est strictement inférieur à tab[i]
on est face à une inversion : on incrémente alors le compteur.
Facile à concevoir cette méthode a un désavantage : elle effectue beaucoup de comparaisons. Par exemple, pour un tableau de dix éléments, le premier sera comparé aux 9 suivants, le deuxième au 8 suivants, le troisième au 7 suivants etc. Il y aura au total 55 comparaisons.
Le cout de cette méthode est quadratique ce qui est pénalisant si l'on souhaite l'utiliser pour de grands tableaux.
Z