Exercice 2 - Coût et tri par insertion · Bac Numérique et Sciences Informatiques Amérique du Nord 2026 (jour 2)

Exercice 2 (6 points)

Cet exercice porte sur la programmation Python en général, la programmation orientée objet en particulier et la structure de données d'arbre.

La WTA (Women’s Tennis Association) est l’instance dirigeante du tennis professionnel international féminin, responsable de l’organisation du circuit « WTA Tour » et de l’établissement des classements mondiaux des joueuses. Dans cet exercice, on ne considère que des matchs de tennis en simple, c’est-à-dire des matchs qui opposent uniquement deux joueuses.

Partie A

On dispose d’une classe Joueuse pour modéliser une joueuse de tennis professionnelle du circuit WTA.

class Joueuse:

def __init__(self, nom, prenom, pays, age, point):

''' nom, prenom et pays sont de type str,

age et point de type int '''

self.nom = nom

self.prenom = prenom

self.pays = pays

self.age = age

# nombre de points WTA

self.point = point

# nombre de victoires

self.victoire = 0

# nombre de défaites

self.defaite = 0

On considère les objets déjà instanciés gauff, paloni, sabalenka et swiatek de la classe Joueuse représentant respectivement les joueuses:

Gauff Coco, américaine, âgée de 20 ans et ayant 6063 points WTA;

Paloni Marta, espagnole, âgée de 23 ans et ayant 4843 points WTA;

Sabalenka Aryna, biélorusse, âgée de 25 ans et ayant 10541 points WTA;

Swiatek Iga, polonaise, âgée de 22 ans et ayant 7470 points WTA.

On souhaite classer les joueuses à l'aide de leurs points WTA. Pour cela il est possible en Python de redéfinir l'opérateur de comparaison < (strictement inférieur) pour les objets de la classe Joueuse en utilisant les points WTA. Ainsi on obtient par exemple:

>>> swiatek < paloni

False

>>> swiatek < sabalenka

True

On utilise une liste Python pour stocker des objets de la classe Joueuse,

liste_joueuses = [swiatek, gauff, paloni, sabalenka, pegula]

que l'on souhaite trier dans l'ordre croissant des points WTA. Pour cela on choisit le tri par insertion dont le code est donné ci-dessous:

def tri_insertion(liste):

for i in range(1, len(liste)):

j = i

while j > 0 and liste[j] < liste[j - 1]:

# échange les valeurs liste[j] et liste[j-1]

liste[j], liste[j - 1] = liste[j - 1], liste[j]

j = j - 1

4.

Préciser, sans justifier, le coût temporel du tri par insertion d'une liste de $n$ éléments dans le pire des cas.

On détaille les étapes du tri par insertion appliqué à la liste liste_joueuses dans le tableau ci-dessous, où chaque ligne correspond à un échange entre deux éléments de la liste.

Étape

Contenu de liste_joueuses

0

[swiatek, gauff, paloni, sabalenka, pegula]

1

[gauff, swiatek, paloni, sabalenka, pegula]

...

...........................................................................

5.

Recopier et compléter le tableau ci-dessus en ajoutant autant de lignes que nécessaires.