On considère dans cet exercices des tableaux d'entiers.
Soit tab un tel tableau. On appelle inversion un couple d'indices distincts iet j tel que :
i est plus petit que j ;
tab[i] est strictement plus grand que tab[j].
Considérons par exemple dans le tableau :
🐍 Script Python
# indices 0 1 2 3tab=[7,5,9,6]
Ce tableau compte 3 inversions :
pour les indices 0 et 1 car tab[0] (qui vaut 7) est strictement supérieur à tab[1] (qui vaut 5),
pour les indices 0 et 3 car tab[0] (qui vaut 7) est strictement supérieur à tab[3] (qui vaut 6),
pour les indices 2 et 3 car tab[2] (qui vaut 9) est strictement supérieur à tab[3] (qui vaut 6).
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 compte 0 inversions.
Les tableaux utilisés dans les tests sont de grande taille (1 000 éléments ou plus). Ainsi, une approche naïve à l'aide d'une double boucle effectuera de trop nombreuses comparaisons (près de 500 000 pour un tableau de 1 000 valeurs !). À titre de comparaison, le corrigé de cet exercice effectue moins de 10 000 comparaisons pour un tableau de même taille.
Afin de mesurer l'efficacité de l'algorithme utilisé, les tests de cet exercice comptent donc le nombre de comparaisons de valeurs effectuées. Le test échoue si ce nombre est supérieur à deux fois le nombre de comparaisons effectuées par l'algorithme du corrigé.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)