Informatique · Première · 2 exercices vérifiés
S’entraîner : Tris par sélection et par insertion
Chapitre : Numérique et sciences informatiques (spécialité)
Ce que vous travaillez
Tri par sélection : à l'étape i, on cherche le minimum de la partie non triée et on l'échange avec l'élément d'indice i ; il effectue toujours n(n − 1)/2 comparaisons. Tri par insertion : on insère chaque élément à sa place dans la partie déjà triée, en décalant les plus grands ; de n − 1 comparaisons (tableau déjà trié) à n(n − 1)/2 (tableau trié à l'envers). Invariant de boucle (« après l'étape i, les i + 1 premiers éléments sont triés »), terminaison, coût quadratique dans le pire cas.
À maîtriser avant de commencer
Ces notions sont utilisées ici. Relisez-les si l’une d’elles vous échappe.
- Parcours séquentiel d'un tableau — Parcourir un tableau élément par élément pour rechercher une occurrence, un extremum (maximum, minimum) ou calculer une moyenne ; le coût est linéaire : le nombre d'opérations est proportionnel à la longueur du tableau, et une recherche d'occurrence examine tout le tableau dans le pire cas.
Comment se déroule la séance
Cette séance s’appuie sur 2 exercices vérifiés. Chacun produit un nouvel énoncé à chaque ouverture, avec une solution calculée.
Formats de réponse : QCM (1), Réponse numérique (1). Difficulté 3 sur 5. Environ 9 minutes pour un premier passage.
Dans votre compte : aide graduée (indice, rappel de cours, aide au démarrage), corrigé pas à pas après chaque tentative, suivi de vos progrès.
Essayez un exercice, sans compte
Un exercice réel de cette séance, le même pour chaque visiteur. Répondez, puis vérifiez : la correction est calculée, et le corrigé s’affiche après votre tentative.
Difficulté 3 sur 5 · ≈ 5 minutes
Énoncé
Le programme Python ci-dessous trie le tableau t par sélection, en comptant les comparaisons dans la variable c.
| n° | Instruction |
|---|---|
| 1 | t = [16, 8, 20, 4, 12, 18] |
| 2 | c = 0 |
| 3 | for i in range(len(t) - 1): |
| 4 | ····m = i |
| 5 | ····for j in range(i + 1, len(t)): |
| 6 | ········c = c + 1 |
| 7 | ········if t[j] < t[m]: |
| 8 | ············m = j |
| 9 | ····t[i], t[m] = t[m], t[i] |
| 10 | print(c) |
Chaque groupe de quatre points « ···· » marque un niveau d'indentation (quatre espaces en Python).
Quel nombre ce programme affiche-t-il ?
Votre réponse
Continuez dans votre compte
Créez votre compte gratuit pour faire toute la séance avec l’aide graduée, ou connectez-vous pour revenir directement ici.
L’accès gratuit comprend les cours et exercices de votre niveau choisi.