#Boucles et contrôleCopier le lien

Les boucles répètent des actions et parcourent des collections sans dupliquer du code. Python propose la boucle for, qui itère sur tout itérable, et la boucle while, qui s'exécute tant qu'une condition reste vraie. Les instructions break et continue affinent le contrôle, et les compréhensions expriment les transformations de collections de façon déclarative.

#PrérequisCopier le lien

Les variables et types du chapitre précédent, en particulier la mutabilité des listes.

#Objectifs d'apprentissageCopier le lien

• Choisir entre for et while selon la nature du problème.
• Utiliser break, continue et la clause else des boucles à bon escient.
• Énoncer la condition de terminaison d'une boucle while avant de l'écrire.
• Écrire des compréhensions et des générateurs pour transformer des collections.

#La boucle forCopier le lien

1for i in range(5):2    print(i)

Sortie :

1021324354

range(5) produit 0, 1, 2, 3, 4. range(1, 11) produit 1 à 10, range(10, 0, -2) produit 10, 8, 6, 4, 2. Le for Python parcourt n'importe quel itérable : liste, chaîne, dictionnaire, fichier ouvert. Pour un index et une valeur simultanément, enumerate est idiomatique :

1fruits = ['pomme', 'poire', 'kiwi']2for i, fruit in enumerate(fruits, start=1):3    print(i, fruit)

Sortie :

11 pomme22 poire33 kiwi

#La boucle whileCopier le lien

1i = 02while i < 3:3    print('i=', i)4    i += 1

Sortie :

1i= 02i= 13i= 2

Le while convient quand le nombre d'itérations n'est pas connu à l'avance : « tant qu'on n'a pas convergé », « tant que l'entrée est invalide ». Avant d'écrire une boucle while, identifiez sa condition de terminaison : la quantité qui diminue strictement (ou croît) à chaque tour et garantit la sortie. Oublier i += 1 donne la boucle infinie classique.

#Invariants de boucleCopier le lien

Une boucle ne se justifie pas seulement par sa condition de terminaison : il faut aussi savoir ce qui est vrai à chaque tour. C'est la notion d'invariant de boucle, l'outil que le cours d'algorithmique utilise pour démontrer qu'un programme fait bien ce qu'il annonce.

Un invariant est une propriété qui porte sur l'état du programme au début de chaque itération. On l'établit par les trois obligations suivantes :

• Initialisation : l'invariant est vrai avant la première itération.
• Conservation : si l'invariant est vrai avant une itération, il reste vrai avant la suivante.
• Terminaison : la boucle se termine, et l'invariant, combiné à la raison d'arrêt, donne la propriété utile sur le résultat.

Les deux premières obligations montrent que l'invariant est vrai à chaque tour ; la troisième est celle qui relie l'invariant au résultat final. Cette démonstration est une récurrence : l'initialisation en est le cas de base, la conservation le pas inductif.

#Exemple : le tri par insertionCopier le lien

Le tri par insertion insère, un par un, chaque élément à sa place dans la partie déjà triée. L'algorithme du cours, écrit ici avec des indices commençant à 0 :

1def tri_insertion(a: list[int]) -> None:2    """Trie a en place (ordre croissant)."""3    for i in range(1, len(a)):4        cle = a[i]              # l'élément à insérer5        j = i - 16        while j >= 0 and a[j] > cle:7            a[j + 1] = a[j]     # décalage vers la droite8            j -= 19        a[j + 1] = cle          # insertion à sa place10 11a = [5, 2, 4, 6, 1, 3]12tri_insertion(a)13print(a)                        # [1, 2, 3, 4, 5, 6]

Invariant : au début de l'itération d'indice i, le sous-tableau a[0:i] contient les éléments initialement en position 0 à i-1, mais rangés dans l'ordre croissant.

• Initialisation : pour i = 1, a[0:1] est réduit à un seul élément, donc trié.
• Conservation : le corps décale vers la droite tous les éléments supérieurs à cle, puis écrit cle dans la première position libre. a[0:i+1] contient alors les éléments d'origine 0..i triés.
• Terminaison : la boucle s'arrête avec i = len(a). En substituant dans l'invariant, a[0:len(a)] — c'est-à-dire tout le tableau — est trié.

Sur [5, 2, 4, 6, 1, 3], les états successifs sont :

1[5 | 2, 4, 6, 1, 3]      i=1, cle=2  ->  [2, 5 | 4, 6, 1, 3]2[2, 5 | 4, 6, 1, 3]      i=2, cle=4  ->  [2, 4, 5 | 6, 1, 3]3[2, 4, 5 | 6, 1, 3]      i=3, cle=6  ->  [2, 4, 5, 6 | 1, 3]4[2, 4, 5, 6 | 1, 3]      i=4, cle=1  ->  [1, 2, 4, 5, 6 | 3]5[1, 2, 4, 5, 6 | 3]      i=5, cle=3  ->  [1, 2, 3, 4, 5, 6]

Le trait vertical sépare la partie triée (à gauche) de la partie non encore traitée.

#Deux invariants plus simplesCopier le lien

Somme d'un tableau. La procédure suivante calcule la somme des éléments ; son invariant est : au début de l'itération d'indice i, somme contient la somme de a[0:i].

1def somme_tableau(a: list[int]) -> int:2    somme = 03    for i in range(len(a)):4        somme = somme + a[i]5    return somme

Initialisation : avant la première itération, somme vaut 0, la somme du sous-tableau vide. Conservation : on ajoute a[i]. Terminaison : somme vaut la somme de a[0:len(a)], soit tout le tableau.

Recherche linéaire. Pour chercher v dans a, l'invariant est : au début de l'itération d'indice i, aucun des éléments a[0:i] n'est égal à v.

1def cherche(a: list[int], v: int) -> int | None:2    for i in range(len(a)):3        if a[i] == v:4            return i        # trouvé : la fonction s'arrête ici5    return None             # parcouru entièrement sans trouver

L'invariant est vrai à l'entrée (aucun élément examiné) et se conserve à chaque tour où l'on ne retourne pas. À la sortie normale, tous les indices ont été examinés : la recherche a échoué, et None est la bonne réponse.

#break, continue, elseCopier le lien

break interrompt immédiatement la boucle ; continue passe à l'itération suivante sans exécuter le reste du corps ; la clause else d'une boucle s'exécute si la boucle s'est terminée normalement, sans break.

1for i in range(6):2    if i % 2 == 1:3        continue        # saute les impairs4    if i == 4:5        break           # sort avant d'afficher 46    print(i)

Sortie :

1022

Le else des boucles est le bon outil pour la recherche : « si on a tout parcouru sans trouver, alors... ».

1def est_premier(n):2    if n < 2:3        return False4    for d in range(2, int(n ** 0.5) + 1):5        if n % d == 0:6            return False        # diviseur trouvé : pas premier7    return True                  # boucle finie sans retour : premier8 9print([n for n in range(2, 30) if est_premier(n)])

Sortie :

1[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

#Compréhensions et générateursCopier le lien

Les compréhensions construisent des collections de manière déclarative : [expression for élément in itérable if condition].

1squares = [x*x for x in range(10) if x % 2 == 0]2print(squares)

Sortie :

1[0, 4, 16, 36, 64]

La même syntaxe décline en dictionnaire ({k: v for ...}) et ensemble ({x for ...}). Un générateur remplace les crochets par des parenthèses : il calcule les valeurs à la demande, sans jamais construire la liste complète, ce qui le rend économe en mémoire sur les grandes séquences :

1def fib(n):2    a, b = 0, 13    while n > 0:4        yield a5        a, b = b, a + b6        n -= 17 8print(list(fib(8)))9print(sum(x*x for x in range(1, 101)))

Sorties :

1[0, 1, 1, 2, 3, 5, 8, 13]2338350

yield transforme la fonction en générateur : chaque appel à next reprend l'exécution juste après le yield précédent. sum(... for ...) consomme le générateur sans matérialiser de liste intermédiaire.

#Complexité : le coût du code qu'on écritCopier le lien

Savoir écrire une boucle ne suffit pas : il faut aussi savoir ce qu'elle coûte. Le modèle de calcul du cours est la machine à accès aléatoire : chaque instruction élémentaire (arithmétique, comparaison, affectation, accès à un élément de tableau) prend un temps constant, et l'on compte le nombre d'instructions en fonction de la taille n de l'entrée.

Trois motifs suffisent à couvrir la plupart des cas.

Une boucle simple parcourt n éléments : coût linéaire. Le corps de for i in range(n) est exécuté n fois, soit Θ(n) instructions.

1a = [3, 1, 4, 1, 5, 9]2total = 03for x in a:          # len(a) itérations4    total += x5print(total)         # 23

Deux boucles imbriquées sur n : coût quadratique. L'itération externe est exécutée n fois, et chacune déclenche n itérations internes : n × n = n².

1n = 52compteur = 03for i in range(n):4    for j in range(n):5        compteur += 16print(compteur)      # 25 = 5²

Trois boucles imbriquées : coût cubique. Le compteur du programme ci-dessous vaut exactement n³, puisque chacune des n valeurs de i déclenche n valeurs de j, chacune déclenchant n valeurs de k :

1n = 42compteur = 03for i in range(1, n + 1):4    for j in range(1, n + 1):5        for k in range(1, n + 1):6            compteur = compteur + 17print(compteur)      # 64 = 4³

Ces trois motifs sont exactement ceux que les épreuves demandent de compter: on ne mesure pas le temps, on compte les exécutions du corps et on exprime le résultat en fonction de n.

La conséquence pratique est brutale : doubler n double le temps d'un algorithme linéaire, le quadruple s'il est quadratique, le multiplie par huit s'il est cubique. C'est la raison pour laquelle le cours compare systématiquement deux algorithmes par leur croissance asymptotique, pas par leur temps mesuré sur une machine.

Deux algorithmes de même complexité peuvent différer par une constante, mais un algorithme de complexité inférieure finit toujours par gagner quand n grandit. Le cours le démontre par un exemple devenu classique : un ordinateur rapide exécutant un tri en n² instructions est battu, sur une grande entrée, par un ordinateur bien plus lent exécutant un tri en n log n. Le facteur décisif n'est pas la vitesse de la machine ni la qualité du code, mais la croissance de la fonction de coût — c'est pourquoi l'analyse asymptotique prime sur la mesure expérimentale.

#Trier : les algorithmes du coursCopier le lien

Le tri est l'exemple fil rouge du cours d'algorithmique : un même problème, plusieurs algorithmes, des coûts très différents. Les quatre versions ci-dessous sont celles du cours.

#Tri par sélectionCopier le lien

À chaque tour, chercher le minimum de la partie non triée et l'échanger avec l'élément courant :

1def tri_selection(a: list[int]) -> None:2    n = len(a)3    for i in range(n - 1):4        mini = i5        for j in range(i + 1, n):6            if a[j] < a[mini]:7                mini = j8        a[i], a[mini] = a[mini], a[i]

Invariant : après le tour i, a[0:i+1] contient les i+1 plus petits éléments du tableau, dans l'ordre. Coût : la boucle interne effectue n-1-i comparaisons au tour i, soit au total

$\sum_{i=0}^{n-2}(n-1-i) = \frac{n(n-1)}{2}$

comparaisons — exactement, quelle que soit l'entrée. Le tri par sélection est donc Θ(n²) dans tous les cas, y compris sur un tableau déjà trié.

#Tri par fusion (merge sort)Copier le lien

Le tri par fusion illustre la stratégie diviser pour régner : on coupe le tableau en deux moitiés, on les trie récursivement, puis on fusionne deux sous-tableaux triés en un seul.

1def fusion(g: list[int], d: list[int]) -> list[int]:2    resultat, i, j = [], 0, 03    while i < len(g) and j < len(d):4        if g[i] <= d[j]:5            resultat.append(g[i]); i += 16        else:7            resultat.append(d[j]); j += 18    resultat.extend(g[i:])      # reste éventuel de g9    resultat.extend(d[j:])      # reste éventuel de d10    return resultat11 12def tri_fusion(a: list[int]) -> list[int]:13    if len(a) <= 1:14        return a                # cas de base : 0 ou 1 élément est trié

Le coût de la fusion est linéaire : chaque comparaison retire un élément d'une des deux listes, donc au plus n comparaisons. La relation de récurrence est T(n) = 2T(n/2) + Θ(n), dont la solution est Θ(n log n) : les deux appels récursifs forment un arbre de log n niveaux, chaque niveau coûtant Θ(n).

L'intérêt de cette analyse est concret. Sur un million d'éléments, le tri par insertion effectue de l'ordre de n² = 10¹² comparaisons, le tri par fusion de l'ordre de n log n ≈ 2 × 10⁷ : le facteur qui compte n'est pas la constante cachée dans le code, c'est la croissance de la fonction de coût. Un algorithme dont le coût croît plus lentement finit toujours par gagner, quelle que soit la qualité de l'implémentation de l'autre.

#Tri par comptage (counting sort)Copier le lien

Quand les valeurs sont des entiers d'un intervalle borné [0, k], on peut trier sans aucune comparaison : on compte les occurrences de chaque valeur, puis on les recopie dans l'ordre.

1def tri_comptage(a: list[int], k: int) -> list[int]:2    c = [0] * (k + 1)3    for x in a:                 # 1. compter les occurrences4        c[x] += 15    for i in range(1, k + 1):   # 2. c[i] = nombre d'éléments <= i6        c[i] += c[i - 1]7    b = [0] * len(a)8    for j in range(len(a) - 1, -1, -1):   # 3. placer de droite à gauche9        c[a[j]] -= 110        b[c[a[j]]] = a[j]11    return b

Le coût est Θ(n + k) : linéaire en la taille de l'entrée et en l'étendue des valeurs. La troisième boucle parcourt le tableau à l'envers, ce qui rend l'algorithme stable : deux éléments de même valeur conservent leur ordre relatif d'origine. Parcourir à l'envers est indispensable — à l'envers, l'élément rencontré en premier pour une valeur donnée est le dernier du tableau d'entrée, et il se retrouve à la position la plus grande.

#RécapitulatifCopier le lien

Le tri par insertion est le meilleur choix sur de petits tableaux ou des tableaux presque triés ; le tri par fusion garantit n log n et reste stable ; le tri par comptage sort du cadre des tris par comparaison, mais exige de connaître l'étendue des valeurs.

#PlaygroundCopier le lien

#ExercicesCopier le lien

1. Calculez la somme des nombres de 1 à N avec range (vérifiez : 5050 pour N = 100).
2. Comptez les voyelles d'une chaîne, sans tenir compte de la casse.
3. Générez la suite de Fibonacci jusqu'à ce que les valeurs dépassent 1000 (boucle while).
4. Réécrivez « liste des carrés pairs des 10 premiers entiers » en compréhension, puis en boucle équivalente.
5. Invariant du tri par insertion. Énoncez l'invariant de la boucle interne (while j >= 0 and a[j] > cle) du tri par insertion et montrez les trois obligations.
6. Coût d'une boucle imbriquée. Écrivez le programme à trois boucles imbriquées de comptage et vérifiez expérimentalement que le compteur vaut n³ pour n = 2, 3, 4, 10.
7. Tri par insertion sur indices 0. Réécrivez le tri par insertion pour un tableau indexé à partir de 0 et tracez son exécution sur [5, 2, 4, 6, 1, 3].
8. Tri par sélection. Écrivez le tri par sélection et comptez le nombre exact de comparaisons pour n = 5. Comparez au tri par insertion sur la même entrée.

#SolutionsCopier le lien

1N = 1002total = 03for k in range(1, N + 1):4    total += k5print(total)          # 50506print(sum(range(1, N + 1)))   # 5050, version idiomatique

1phrase = "Bonjour le monde"2nb = sum(1 for c in phrase.lower() if c in 'aeiouy')3print(nb)             # 6

1fibs = [0, 1]2while fibs[-1] <= 1000:3    fibs.append(fibs[-1] + fibs[-2])4print(fibs)5# [0, 1, 1, 2, ..., 987, 1597]

1pairs_comp = [x*x for x in range(10) if x % 2 == 0]2 3pairs_boucle = []4for x in range(10):5    if x % 2 == 0:6        pairs_boucle.append(x*x)7 8print(pairs_comp == pairs_boucle)   # True

1for n in (2, 3, 4, 10):2    compteur = 03    for i in range(1, n + 1):4        for j in range(1, n + 1):5            for k in range(1, n + 1):6                compteur = compteur + 17    print(n, compteur, n ** 3)8# 2 8 89# 3 27 2710# 4 64 6411# 10 1000 1000

1def tri_insertion(a: list[int]) -> None:2    for i in range(1, len(a)):3        cle = a[i]4        j = i - 15        while j >= 0 and a[j] > cle:6            a[j + 1] = a[j]7            j -= 18        a[j + 1] = cle9 10a = [5, 2, 4, 6, 1, 3]11tri_insertion(a)12print(a)     # [1, 2, 3, 4, 5, 6]

1def tri_selection(a: list[int]) -> None:2    n = len(a)3    for i in range(n - 1):4        mini = i5        for j in range(i + 1, n):6            if a[j] < a[mini]:7                mini = j8        a[i], a[mini] = a[mini], a[i]9 10a = [5, 2, 4, 1, 3]11tri_selection(a)12print(a)     # [1, 2, 3, 4, 5]