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 que j ;
• tab[i] est strictement plus grand que tab[j].

Considérons par exemple dans le tableau :

🐍 Script Python

# indices  0  1  2  3
tab     = [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).

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

🐍 Console Python

>>> inversions([])
0
>>> inversions([5, 6, 7, 9])
0
>>> inversions([7, 5, 9, 6])
3

###

Lancerfrom random import sample, randintbksl-nlbksl-nlbksl-nldef py-undinversions(tab):bksl-nl if len(tab) <= 1:bksl-nl return 0bksl-nlbksl-nl N = len(tab)bksl-nl gauche = tab[: N // 2]bksl-nl droite = tab[N // 2 :]bksl-nl invpy-undgauche = py-undinversions(gauche)bksl-nl invpy-unddroite = py-undinversions(droite)bksl-nlbksl-nl total = 0bksl-nl ipy-undgauche = 0bksl-nl ipy-unddroite = 0bksl-nl ipy-undtab = 0bksl-nlbksl-nl while ipy-undgauche < len(gauche) and ipy-unddroite < len(droite):bksl-nl if gauche[ipy-undgauche] <= droite[ipy-unddroite]:bksl-nl tab[ipy-undtab] = gauche[ipy-undgauche]bksl-nl ipy-undgauche += 1bksl-nl else:bksl-nl total += len(gauche) - ipy-undgauchebksl-nl tab[ipy-undtab] = droite[ipy-unddroite]bksl-nl ipy-unddroite += 1bksl-nl ipy-undtab += 1bksl-nlbksl-nl while ipy-undgauche < len(gauche):bksl-nl tab[ipy-undtab] = gauche[ipy-undgauche]bksl-nl ipy-undgauche += 1bksl-nl ipy-undtab += 1bksl-nlbksl-nl while ipy-unddroite < len(droite):bksl-nl tab[ipy-undtab] = droite[ipy-unddroite]bksl-nl ipy-unddroite += 1bksl-nl ipy-undtab += 1bksl-nlbksl-nl return invpy-undgauche + invpy-unddroite + totalbksl-nlbksl-nlbksl-nl# Testsbksl-nlassert inversions([]) == 0bksl-nlassert inversions([5, 6, 7, 9]) == 0bksl-nlassert inversions([7, 5, 9, 6]) == 3bksl-nlbksl-nl# Tests supplémentairesbksl-nlmaximum = 10py-strpy-str3bksl-nlfor py-und in range(20):bksl-nl tab = sample(range(maximum), randint(0, 100))bksl-nl attendu = py-undinversions(tab[:])bksl-nl solution = inversions(tab[:])bksl-nl assert solution == attendu, f"Erreur avec {tab}"bksl-nlbksl-nl Valider 5/5 TéléchargerTéléverser RechargerSauvegarder

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