Exercice 1 - Tri par sélection et coût · Bac Numérique et Sciences Informatiques Centres étrangers (Afrique) 2026 (jour 1)

Exercice 1 (6 points)

Cet exercice porte sur les algorithmes de tri et d'un parcours d'arbre binaire de recherche et sur la programation orientée objet

Contexte

Un club d’athlétisme organise une compétition inter-scolaire regroupant quatre disciplines:

le 100 mètres;

le saut en longueur;

le lancer du poids;

le 1500 mètres.

Chaque athlète réalise une performance dans chacune de ces épreuves. Pour établir le classement final, un score global est calculé à partir de ses résultats selon des règles de conversion simples. L’objectif du programme est de modéliser ces athlètes et d’implémenter différentes méthodes de tri pour les classer du premier au dernier.

Le score d’un athlète est la somme des points obtenus dans chaque épreuve. Ces points s’obtiennent selon les règles suivantes:

points du 100 m: $(20 - t) * 10$ avec $t$ le temps en secondes;

points du saut en longueur: $d * 20$ avec $d$ la distance en mètres;

points du lancer de poids: $d * 10$ avec $d$ la distance en mètres;

points du 1500 m: $(500 - t) * 1$ avec $t$ le temps en secondes.

Pour obtenir le classement des athlètes du plus grand score au plus petit score, on réorganise la liste l des athlètes avec la fonction classer(l) qui prend en paramètre la liste l d'athlètes:

def classer(l):

n = len(l)

for i in range(n):

max_index = i

for j in range(i + 1, n):

if...:

max_index = j

temp = l[i]

l[i] = l[max_index]

l[max_index] = temp

4.

Recopier et compléter la ligne 6 de la fonction classer (condition du if):

5.

Parmi les propositions suivantes, choisir celle qui correspond au type de tri effectué par la fonction classer:

6.

Donner le coût de la fonction classer, c'est-à-dire le nombre de comparaisons d'éléments de la liste, en fonction de la taille $n$ de la liste: