Tri, recherche et coût des programmes

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• mesurer honnêtement le temps d'exécution d'un morceau de programme avec time.perf_counter, et dire pourquoi une mesure de temps ne caractérise pas un algorithme;
• instrumenter un programme avec un compteur pour compter ses opérations plutôt que ses secondes, et choisir entre les deux selon la question posée;
• écrire et tracer la recherche séquentielle et la recherche dichotomique, énoncer l'invariant de la seconde et justifier son coût en $\lfloor {\log }_{2}n\rfloor +1$ comparaisons;
• écrire, tracer et instrumenter le tri par sélection et le tri par insertion, et comparer leurs cas favorable, moyen et défavorable sur des mesures et non sur des impressions;
• reconnaître qu'un coût «croît comme $n^2$» ou «comme $\log n$», et lire la notation $O$ comme une manière de dire cela;
• utiliser sorted, list.sort et le paramètre key plutôt que d'écrire votre propre tri, et dire ce que Python fait réellement à votre place;
• traiter une fonction comme une valeur, la passer en argument, et écrire une lambda comme clé de sorted, min ou max.

Deux programmes, une même réponse

Voici un problème que vous savez résoudre depuis le chapitre 3: calculer la somme des entiers de 1 à $n$. Et voici deux programmes qui le résolvent.

def somme_boucle(n):
    """Somme des entiers de 1 a n, en les additionnant un par un."""
    total = 0
    for i in range(1, n + 1):
        total = total + i
    return total


def somme_formule(n):
    """Somme des entiers de 1 a n, par la formule n(n+1)/2."""
    return n * (n + 1) // 2


print(somme_boucle(1000

500500
500500
True

Les deux donnent la même réponse. Les deux sont corrects. Jusqu'ici, le cours s'est arrêté là: un programme qui donne la bonne réponse est un bon programme. Ce chapitre ajoute une seconde question, qui est celle de toute l'informatique appliquée: est-ce que l'un des deux est meilleur que l'autre, et en quel sens?

Intuitivement, oui. La première fonction fait $n$ additions; la seconde en fait trois, quelle que soit la valeur de $n$. Pour $n=1000$, la différence est imperceptible. Pour $n=10^9$, la première fonction demanderait plusieurs minutes et la seconde resterait instantanée. La différence n'est donc pas une question de style: c'est la différence entre un programme utilisable et un programme inutilisable.

Ce chapitre apprend à transformer cette intuition en quelque chose que l'on peut mesurer, puis en quelque chose que l'on peut prédire. Mesurer, c'est chronométrer: on lance le programme et on regarde sa montre. Prédire, c'est compter: on regarde le programme et on dit combien d'opérations il fera avant même de le lancer. Les deux sont utiles, et ils ne répondent pas à la même question.

Le mot algorithme (algorithm) désigne ici la méthode, indépendamment du programme qui l'écrit: «additionner un par un» est un algorithme, somme_boucle en est une réalisation en Python. Le même algorithme peut être écrit en Python, en C ou sur une feuille de papier; il fera le même nombre d'additions dans les trois cas, mais pas dans le même temps.

Le reste du chapitre applique cette double mesure à deux problèmes que vous rencontrerez partout: chercher une valeur dans une collection, et trier une collection.

Mesurer: le temps d'exécution

Le chronomètre de Python

Le module time de la bibliothèque standard fournit perf_counter, un compteur de haute résolution. Il ne donne pas l'heure: il donne un nombre de secondes depuis un instant arbitraire. Seules les différences entre deux appels ont un sens, et c'est exactement ce dont nous avons besoin.

import time

debut = time.perf_counter()
somme_boucle(1000000)
fin = time.perf_counter()
print("boucle  :", fin - debut, "s")

debut = time.perf_counter()
somme_formule(1000000)
fin = time.perf_counter()
print("formule :", fin - debut, "s")

boucle  : 0.09840004198485985 s
formule : 1.8750433810055256e-06 s

Le schéma est toujours le même: on relève l'heure avant, on relève l'heure après, on soustrait. La notation 1.8750433810055256e-06 est l'écriture scientifique de Python: elle signifie $1,875\times 10^{-6}$, soit un peu moins de deux microsecondes.

La conclusion semble nette: la boucle met environ 0,098 seconde, la formule environ deux microsecondes, soit un rapport de l'ordre de 50 000. Sauf que ce chiffre est faux, ou du moins il n'est pas reproductible. Voici la sortie du même programme relancé immédiatement après, sur la même machine, sans rien changer:

boucle  : 0.03870400000596419 s
formule : 2.2080494090914726e-06 s

La boucle a mis 0,0387 s au lieu de 0,0984 s: deux mesures du même code, dans un rapport de 2,5. Aucune des deux n'est «la» durée du programme.

Toutes les durées de ce chapitre ont été mesurées sur un ordinateur portable à processeur ARM 64 bits sous macOS, avec CPython 3.13. Sur votre machine, les nombres seront différents; les rapports entre eux devraient rester du même ordre, et c'est la seule chose que nous en tirerons.

Chronométrer honnêtement

Trois précautions suffisent à rendre une mesure de temps défendable.

1. Répéter. Une mesure isolée ne dit rien. On exécute le code plusieurs fois et on retient le minimum, pas la moyenne: les perturbations extérieures ne peuvent que ralentir le programme, jamais l'accélérer, donc le minimum est la mesure la moins polluée.
2. Jeter le premier tour. Le premier appel paie l'entrée du code dans le cache du processeur et diverses initialisations. On l'exécute et on l'ignore: c'est le «tour de chauffe».
3. Dire sur quelle machine. Une durée sans machine est une affirmation invérifiable.

Nous pouvons emballer tout cela dans une fonction. Elle reçoit en paramètre la fonction à mesurer elle-même, ce que Python permet parce qu'une fonction est une valeur comme une autre; la section consacrée au paramètre key de sorted reviendra en détail sur cette idée.

import time


def chronometre(fonction, argument, repetitions=5):
    """Mesure fonction(argument) plusieurs fois et renvoie le meilleur temps."""
    fonction(argument)                      # tour de chauffe: on le jette
    mesures = []
    for _ in range(repetitions):
        debut = time.perf_counter()
        fonction(argument)
        fin = time.perf_counter()
        mesures.append(fin - debut)
    return min(mesures)

Le nom _ est une variable comme une autre; par convention, on l'emploie quand on n'a pas besoin de sa valeur — ici le numéro de la répétition ne sert à rien.

Compter: les opérations élémentaires

Puisque les secondes dépendent de la machine, comptons plutôt ce qui n'en dépend pas. La technique est élémentaire et vous l'avez déjà pratiquée au chapitre 3: on ajoute un compteur, une variable entière que l'on incrémente à chaque opération que l'on veut compter.

def somme_comptee(n):
    """Somme des entiers de 1 a n, en comptant les additions effectuees."""
    total = 0
    additions = 0
    for i in range(1, n + 1):
        total = total + i
        additions = additions + 1
    return total, additions


for n in [10, 100, 1000, 

n =      10 : somme =             55 , additions = 10
n =     100 : somme =           5050 , additions = 100
n =    1000 : somme =         500500 , additions = 1000
n = 1000000 : somme =   500000500000 , additions = 1000000

Le résultat est sans surprise et c'est précisément ce qui en fait sa valeur: le nombre d'additions vaut exactement $n$, il vaut $n$ sur toutes les machines, dans toutes les versions de Python, aujourd'hui et dans dix ans. La fonction somme_formule, elle, fait une multiplication, une addition et une division entière: trois opérations, quelle que soit la valeur de $n$. On tient là une comparaison qui ne dépend plus de rien d'extérieur à l'algorithme.

Pourquoi la comparaison plutôt que l'addition ou l'affectation? Parce que c'est elle qui fait le travail: chercher et trier consistent à comparer des éléments entre eux. Et parce que, dans un programme réel, comparer deux objets peut être très cher (comparer deux chaînes de dix mille caractères, deux dates, deux enregistrements), alors que déplacer une référence est bon marché. Compter les comparaisons, c'est compter ce qui dominera le coût.

Les deux mesures se complètent, et il vaut la peine de savoir laquelle employer:

Le chronomètre répond à une question d'ingénieur: ce programme tient-il dans le temps dont je dispose, sur la machine dont je dispose? Le compteur répond à une question de conception: cette méthode passera-t-elle à l'échelle? Un programme qui traite 1000 clients en une seconde et qu'il faudra faire tourner sur un million de clients ne sera pas sauvé par une machine trois fois plus rapide si son coût croît comme $n^2$.

La recherche séquentielle

Le problème et l'algorithme

Premier problème: étant donné une liste et une valeur, dire si la valeur est dans la liste et, si oui, à quel indice. Python sait le faire avec in et index, mais nous allons l'écrire nous-mêmes pour pouvoir en compter le coût.

La méthode évidente est celle que vous appliqueriez pour trouver un nom dans une liste non classée: regarder le premier élément, puis le deuxième, jusqu'à trouver ou à épuiser la liste. C'est la recherche séquentielle (linear search).

def recherche_sequentielle(tableau, cible):
    """Renvoie l'indice de cible dans tableau, ou -1 si elle est absente."""
    for i in range(len(tableau)):
        if tableau[i] == cible:
            return i
    return -1

La convention -1 pour «absent» est celle de la fonction find des chaînes de caractères, vue au chapitre 5; on aurait pu renvoyer None. Notez que le return i à l'intérieur de la boucle sort immédiatement de la fonction: c'est ce qui rend la recherche rapide quand la cible est au début.

Pour compter, on ajoute un compteur et on le renvoie à côté du résultat, sous forme de tuple (chapitre 6).

def recherche_sequentielle_comptee(tableau, cible):
    """Meme algorithme, en comptant les comparaisons avec la cible."""
    comparaisons = 0
    for i in range(len(tableau)):
        comparaisons = comparaisons + 1
        if tableau[i] == cible:
            return i, comparaisons
    return -1, comparaisons

Les trois cas

Faisons tourner cette version sur le tableau de référence de ce cours, [38, 27, 43, 3, 9, 82, 10] — sept nombres fictifs, choisis une fois pour toutes et réutilisés tel quel par le cours «Information, calcul et communication».

tableau = [38, 27, 43, 3, 9, 82, 10]
for cible in [38, 3, 10, 100]:
    indice, comparaisons = recherche_sequentielle_comptee(tableau, cible)
    print(f"cible {cible:>3} : indice {indice:>2} , 

cible  38 : indice  0 , 1 comparaisons
cible   3 : indice  3 , 4 comparaisons
cible  10 : indice  6 , 7 comparaisons
cible 100 : indice -1 , 7 comparaisons

Ces quatre lignes contiennent toute l'analyse.

• Cas favorable (best case): la cible est en première position. Une seule comparaison, quel que soit $n$.
• Cas défavorable (worst case): la cible est en dernière position, ou elle est absente. Il faut $n$ comparaisons, ici 7. C'est le cas le plus important, parce qu'il donne une garantie: quoi qu'il arrive, la recherche ne coûtera jamais plus que cela.
• Cas moyen (average case): si la cible est présente et que chaque position est également probable, on fait $1,2,\dots ,n$ comparaisons avec probabilité $1/n$ chacune, soit en moyenne

comparaisons, soit environ la moitié du tableau.

Vérifions cette dernière formule par la mesure, en cherchant successivement chacun des sept éléments présents.

tableau = [38, 27, 43, 3, 9, 82, 10]
total = 0
for cible in tableau:
    _, comparaisons = recherche_sequentielle_comptee(tableau, cible)
    total = total + comparaisons
print("total :", total)
print("moyenne sur les 7 elements presents :", total / len(tableau))

total : 28
moyenne sur les 7 elements presents : 4.0

La formule (10.1) donne $(7+1)/2=4$: la mesure et le calcul coïncident. Le total 28 est d'ailleurs la somme $1+2+\cdots +7$, celle du programme d'ouverture du chapitre.

L'essentiel est ailleurs: dans les trois cas, le coût est proportionnel à $n$ (ou constant, dans le cas favorable). Doubler la taille du tableau double le travail. Pour un tableau d'un million d'éléments, une recherche infructueuse coûte un million de comparaisons. Si votre programme fait cela pour chacun de ses dix mille utilisateurs, vous en êtes à dix milliards de comparaisons, et vous avez un problème.

La recherche dichotomique

L'idée: exploiter l'ordre

Reprenez le réflexe de l'annuaire papier. Pour trouver «Müller», personne ne commence à la lettre A: on ouvre au milieu, on regarde la lettre, et on jette d'un coup la moitié du volume. C'est la recherche dichotomique (binary search), et elle exige une condition: le tableau doit être trié.

Le tableau du cours, trié, devient [3, 9, 10, 27, 38, 43, 82]. Cherchons-y la valeur 10. L'algorithme maintient deux bornes, gauche et droite, qui délimitent la portion du tableau où la cible peut encore se trouver. À chaque tour, il regarde l'élément du milieu:

• si c'est la cible, c'est fini;
• si l'élément du milieu est plus petit que la cible, alors, le tableau étant trié, la cible ne peut être que à droite: on remonte gauche;
• sinon la cible ne peut être que à gauche: on descend droite.

Dans les deux derniers cas, on élimine d'un coup la moitié des candidats restants.

def recherche_dichotomique(tableau, cible):
    """Cherche cible dans un tableau TRIE. Renvoie son indice, ou -1."""
    gauche = 0
    droite = len(tableau) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if tableau[milieu] == cible:
            return milieu
        elif tableau[milieu] < cible:
            gauche = milieu + 1
        else

Trois détails méritent l'attention. La division entière // du chapitre 1 est indispensable: (gauche + droite) / 2 donnerait un flottant et tableau[3.0] provoquerait une TypeError. Le + 1 et le - 1 sont ce qui garantit la terminaison: sans eux, si le milieu tombe sur gauche, l'intervalle ne rétrécirait pas et la boucle tournerait indéfiniment — la faute du chapitre 3. Enfin, la condition d'arrêt gauche <= droite autorise l'intervalle d'un seul élément; avec un < strict, on manquerait les cibles isolées.

La trace, étape par étape

L'invariant, et pourquoi le tableau doit être trié

Ce qui fait fonctionner l'algorithme est une propriété vraie avant chaque tour de boucle et préservée par chaque tour: c'est un invariant de boucle, la notion du chapitre 3.

Le rôle de l'hypothèse «trié» saute aux yeux dans la démonstration: c'est elle, et elle seule, qui autorise à éliminer une moitié entière sur la foi d'une seule comparaison. Appliquée à un tableau non trié, la fonction ne plante pas — elle répond faux, ce qui est bien pire.

non_trie = [38, 27, 43, 3, 9, 82, 10]
print("43 est bien dans la liste :", 43 in non_trie)
print("recherche_dichotomique(non_trie, 43) :", recherche_dichotomique(non_trie, 43))

43 est bien dans la liste : True
recherche_dichotomique(non_trie, 43) : -1

La version récursive

Le chapitre 9 a montré qu'une méthode «réduire le problème à un problème plus petit du même type» s'écrit naturellement de façon récursive. La dichotomie en est l'exemple canonique: chercher dans un intervalle, c'est chercher dans une moitié de cet intervalle.

def dichotomique_recursive(tableau, cible, gauche, droite):
    """Cherche cible dans tableau[gauche..droite], suppose trie."""
    if gauche > droite:
        return -1                         # cas de base: intervalle vide
    milieu = (gauche + droite) // 2
    if tableau[milieu] == cible:
        return milieu                     # second cas de base: trouve
    elif tableau[milieu] < cible:
        return dichotomique_recursive(tableau, cible, milieu + 1, droite)
    else:
        return

trie = [3, 9, 10, 27, 38, 43, 82]
print(dichotomique_recursive(trie, 10, 0, len(trie) - 1))
print(dichotomique_recursive(trie, 5, 0, len(trie) - 1))

2
-1

La première sortie est l'indice de 10, la seconde le $-1$ qui signale l'absence de 5. La version récursive a deux cas de base — l'intervalle vide et la cible trouvée — et un seul appel récursif par niveau, contrairement à fibonacci du chapitre 9 qui en faisait deux. La pile d'appels atteint donc une profondeur de $\lfloor {\log }_{2}n\rfloor +1$ seulement: environ 20 niveaux pour un million d'éléments, très loin de la limite de récursion de Python. Les deux versions font exactement le même nombre de comparaisons; la version itérative est un peu plus rapide parce qu'elle évite les appels de fonction, la version récursive est plus courte à lire. Choisissez selon ce qui rend votre programme plus clair.

Le logarithme, mesuré

La formule (10.2) est une affirmation vérifiable. Vérifions-la, en cherchant toutes les valeurs possibles d'un tableau trié de taille $n$ et en retenant le maximum de comparaisons.

Il faut d'abord une version comptée, comme pour la recherche séquentielle: un compteur incrémenté à chaque élément du milieu examiné.

def recherche_dichotomique_comptee(tableau, cible):
    """Meme algorithme, en comptant les elements examines."""
    gauche = 0
    droite = len(tableau) - 1
    comparaisons = 0
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        comparaisons = comparaisons + 1
        if tableau[milieu] == cible:
            return milieu, comparaisons
        elif tableau[milieu] 

import math

print(f"{'n':>7} {'dicho max':>10} {'log2(n)+1':>10} {'sequentiel max':>15}")
for n in [10, 100, 1000, 10000, 100000, 1000000]:
    trie = list(range(n))

      n  dicho max  log2(n)+1  sequentiel max
     10          4          4              10
    100          7          7             100
   1000         10         10            1000
  10000         14         14           10000
 100000         17         17          100000
1000000         20         20         1000000

La colonne mesurée et la colonne calculée coïncident sur toute la plage, du plus petit au plus grand tableau: la formule n'est pas une approximation, c'est le nombre exact d'éléments examinés au pire. La vérification a été poussée plus loin que ce que montre le tableau: pour toutes les tailles de 1 à 2000, en cherchant successivement toutes les cibles présentes et toutes les cibles absentes, le maximum mesuré vaut $\lfloor {\log }_{2}n\rfloor +1$ sans une seule exception.

Lisez maintenant la colonne de gauche et celle de droite ensemble. Le tableau est multiplié par dix à chaque ligne, et:

• la recherche séquentielle multiplie son coût par dix — 10, 100, 1000, 10 000…;
• la recherche dichotomique ajoute trois comparaisons — 4, 7, 10, 14, 17, 20.

C'est la signature du logarithme: une multiplication de l'argument devient une addition sur le résultat, parce que ${\log }_2(10n)={\log }_{2}n+{\log }_{2}10\approx {\log }_{2}n+3,32$. Pour un million d'éléments, vingt comparaisons suffisent, soit 50 000 fois moins que la recherche séquentielle. Et pour un milliard d'éléments, il en faudrait trente.

L'explorateur ci-dessous laisse déplacer la taille du tableau sur toute cette plage. Observez la barre supérieure: l'intervalle encore à fouiller descend en marches d'escalier régulières jusqu'à un seul élément, et le nombre de marches — donc de comparaisons — augmente très lentement quand $n$ augmente. Le readout «rapport» donne le facteur entre les deux recherches: 2,5 pour dix éléments, 50 000 pour un million.

Trier: deux algorithmes élémentaires

La dichotomie exige un tableau trié. Reste donc à savoir trier — et c'est le problème sur lequel l'informatique a le plus écrit, parce qu'il est simple à énoncer et qu'il admet des solutions de coûts très différents.

Nous allons en voir deux, les deux que l'on apprendrait à un enfant qui trie des cartes. Tous deux travaillent en place, c'est-à-dire en réarrangeant la liste elle-même. Nos versions travailleront prudemment sur une copie (t = list(tableau), chapitre 6), pour ne pas modifier l'argument de l'appelant à son insu — le piège de l'aliasing.

Le tri par sélection

L'idée: chercher le plus petit élément de tout le tableau et l'échanger avec la première case; puis chercher le plus petit du reste et l'échanger avec la deuxième case; et ainsi de suite. Après $k$ passes, les $k$ premières cases contiennent, triées, les $k$ plus petits éléments.

def tri_selection(tableau):
    """Trie une copie du tableau par selection du minimum."""
    t = list(tableau)
    n = len(t)
    for i in range(n - 1):
        indice_min = i
        for j in range(i + 1, n):
            if t[j] < t[indice_min]:
                indice_min = j
        if indice_min !=

L'échange t[i], t[indice_min] = t[indice_min], t[i] est l'affectation multiple du chapitre 6: Python évalue d'abord le membre de droite en entier, donc aucune variable temporaire n'est nécessaire. La boucle extérieure s'arrête à n - 1 et non à n: quand il ne reste qu'un élément, il est forcément à sa place.

Voici ce que fait l'algorithme sur le tableau du cours, une ligne par passe.

t = [38, 27, 43, 3, 9, 82, 10]
n = len(t)
print("depart      :", t)
for i in range(n - 1):
    indice_min = i
    for j in range(i + 1, n):
        if

depart      : [38, 27, 43, 3, 9, 82, 10]
passe 0 : min = 3 (indice 3) -> [3, 27, 43, 38, 9, 82, 10]
passe 1 : min = 9 (indice 4) -> [3, 9, 43, 38, 27, 82, 10]
passe 2 : min = 10 (indice 6) -> [3, 9, 10, 38, 27, 82, 43]
passe 3 : min = 27 (indice 4) -> [3, 9, 10, 27, 38, 82, 43]
passe 4 : min = 38 (indice 4) -> [3, 9, 10, 27, 38, 82, 43]
passe 5 : min = 43 (indice 6) -> [3, 9, 10, 27, 38, 43, 82]

La passe 4 est instructive: le minimum du reste, 38, se trouvait déjà à sa place, indice_min valait i et le test if indice_min != i a évité un échange inutile. Le tableau n'a pas changé entre les lignes «passe 3» et «passe 4», et pourtant la passe a bien eu lieu — elle a fait ses comparaisons.

Le tri par insertion

L'idée: celle du joueur de cartes qui range sa main. On prend les éléments un par un, de gauche à droite, et on insère chacun à sa place dans la partie déjà triée, en décalant vers la droite tous ceux qui sont plus grands que lui.

def tri_insertion(tableau):
    """Trie une copie du tableau en inserant chaque element a sa place."""
    t = list(tableau)
    for i in range(1, len(t)):
        valeur = t[i]
        j = i - 1
        while j >= 0 and t[j] > valeur:
            t[j + 1] = t[j]                 # on decale vers la droite
            j =

Deux points méritent d'être compris plutôt qu'appris. D'abord, valeur = t[i] met la valeur de côté avant de décaler: sans cela, le premier décalage l'écraserait. Ensuite, le and de la condition j >= 0 and t[j] > valeur est un court-circuit (chapitre 2): si j vaut -1, Python n'évalue même pas t[j], et c'est heureux, car t[-1] désignerait le dernier élément de la liste et l'algorithme partirait en vrille. L'ordre des deux tests n'est donc pas interchangeable.

t = [38, 27, 43, 3, 9, 82, 10]
print("depart      :", t)
for i in range(1, len(t)):
    valeur = t[i]
    j = i - 1
    while j >= 0 and t[j] > valeur:

depart      : [38, 27, 43, 3, 9, 82, 10]
i = 1 (valeur 27) -> [27, 38, 43, 3, 9, 82, 10]
i = 2 (valeur 43) -> [27, 38, 43, 3, 9, 82, 10]
i = 3 (valeur  3) -> [3, 27, 38, 43, 9, 82, 10]
i = 4 (valeur  9) -> [3, 9, 27, 38, 43, 82, 10]
i = 5 (valeur 82) -> [3, 9, 27, 38, 43, 82, 10]
i = 6 (valeur 10) -> [3, 9, 10, 27, 38, 43, 82]

Comparez avec la trace du tri par sélection: le tri par insertion a laissé le tableau inchangé aux tours $i=2$ et $i=5$, parce que 43 et 82 étaient déjà plus grands que tout ce qui les précédait. Une seule comparaison a suffi pour le constater. Le tri par sélection, lui, aurait de toute façon parcouru tout le reste du tableau. Cette différence est le cœur de la comparaison qui suit.

Les compteurs

Instrumentons les deux tris. Pour la sélection nous comptons les comparaisons entre éléments et les échanges; pour l'insertion, les comparaisons et les décalages (chaque écriture d'une case vers la droite).

def tri_selection_compte(tableau):
    """Meme tri, en comptant les comparaisons et les echanges."""
    t = list(tableau)
    n = len(t)
    comparaisons = 0
    echanges = 0
    for i in range(n - 1):
        indice_min = i
        for j in range(i + 1, n):
            comparaisons = comparaisons +

def tri_insertion_compte(tableau):
    """Meme tri, en comptant les comparaisons et les decalages."""
    t = list(tableau)
    comparaisons = 0
    decalages = 0
    for i in range(1, len(t)):
        valeur = t[i]
        j = i - 1
        while j >= 0:
            comparaisons = comparaisons + 1

La boucle while j >= 0: suivie d'un break remplace ici le and court-circuité, uniquement pour pouvoir incrémenter le compteur juste avant la comparaison; l'algorithme est identique.

Cas favorable et cas défavorable, mesurés

La différence est spectaculaire dès que les données sont grandes. Fabriquons une liste de 2000 nombres pseudo-aléatoires (fictifs, avec une graine fixée pour que l'expérience soit reproductible), puis une liste «presque triée» obtenue en triant la première et en y dérangeant vingt valeurs seulement.

import random

random.seed(10)
n = 2000
aleatoire = [random.randint(0, 9999) for _ in range(n)]
presque_triee = sorted(aleatoire)
for _ in range(20):                      # on derange 20 valeurs seulement
    i = random.randrange(n)
    presque_triee[i] = random.randint(0, 9999)

aleatoire    : selection  1999000 comparaisons, insertion  1004264
presque trie : selection  1999000 comparaisons, insertion    16318

Sur des données aléatoires, le tri par insertion fait à peu près la moitié des comparaisons du tri par sélection: en moyenne, chaque élément ne remonte que la moitié de la partie déjà triée, d'où $n(n-1)/4=999500$ comparaisons attendues contre 1 004 264 mesurées, un écart de 0,5 %. Sur des données presque triées, il en fait 16 318 au lieu de 1 999 000, soit 122 fois moins, tandis que le tri par sélection ne bouge pas d'une comparaison.

Premières notions de complexité

Ce qui compte, c'est la forme de la croissance

Rassemblons les formules obtenues, toutes mesurées dans ce chapitre:

Regardez ces expressions de loin, en plissant les yeux. Les constantes et les termes secondaires n'ont pas d'importance: $n(n-1)/2$ et $n^2/4$ se comportent de la même façon quand $n$ grandit, et ni l'un ni l'autre ne ressemble à $n$ ou à ${\log }_{2}n$. Ce qui compte, c'est la forme de la croissance, et la question à laquelle elle répond est: si je multiplie la taille des données par 10, par combien le travail est-il multiplié?

• Un coût en ${\log }_{2}n$: le travail augmente de 3 ou 4 unités. Multiplier les données par 1000 coûte dix comparaisons de plus.
• Un coût en $n$ (dit linéaire): le travail est multiplié par 10.
• Un coût en $n^2$ (dit quadratique): le travail est multiplié par 100.

Cette dernière ligne est la raison pour laquelle on n'utilise pas les tris de ce chapitre sur de grandes données. Vérifions-la, en mesurant à la fois les comparaisons et le temps du tri par sélection sur des tailles doublées.

random.seed(10)
precedent = None
for n in [500, 1000, 2000, 4000]:
    donnees = [random.randint(0, 9999) for _ in range(n)]
    t = chronometre(tri_selection, donnees)
    _, comparaisons, _ = tri_selection_compte(donnees)
    rapport = "-" if precedent is None else

n =  500 :    124750 comparaisons, 0.0046 s, rapport -
n = 1000 :    499500 comparaisons, 0.0172 s, rapport 3.8
n = 2000 :   1999000 comparaisons, 0.0681 s, rapport 4.0
n = 4000 :   7998000 comparaisons, 0.3022 s, rapport 4.4

Les comparaisons quadruplent exactement: $499500/124750=4,004$, puis $4,002$, puis $4,001$. Les temps quadruplent approximativement: 3,8 puis 4,0 puis 4,4. C'est la double leçon de ce chapitre en une seule sortie — le comptage donne la loi, le chronomètre la confirme avec du bruit. Si l'on n'avait que la colonne des secondes, on hésiterait entre «×4» et «×4,5»; la colonne des comparaisons, elle, ne laisse aucun doute.

La figure 10.3 rassemble sur un même graphique les quatre coûts établis dans ce chapitre. Les deux axes y sont en échelle logarithmique, sans quoi la courbe de la dichotomie serait plaquée contre l'axe horizontal et invisible à côté de celles des tris. Dans ces coordonnées, un coût qui croît comme une puissance de $n$ devient une droite dont la pente est l'exposant: pente 2 pour les tris, pente 1 pour la recherche séquentielle, pente presque nulle pour la dichotomie.

La notation O, prudemment

Les informaticiens ont une notation pour dire «croît comme».

Avec cette notation, le chapitre se résume en cinq lignes:

• recherche dichotomique: $O(\log n)$;
• recherche séquentielle: $O(n)$;
• tri par insertion sur des données déjà triées: $O(n)$;
• tri par sélection: $O(n^2)$, dans tous les cas;
• tri par insertion: $O(n^2)$ au pire et en moyenne, $O(n)$ au mieux.

La base du logarithme a disparu de la quatrième ligne, et c'est volontaire: passer de ${\log }_2$ à ${\log }_{10}$ revient à diviser par ${\log }_{2}10\approx 3,32$, c'est-à-dire à changer une constante multiplicative, que la notation ignore. On écrit donc $O(\log n)$ sans préciser la base.

Deux mises en garde, pour finir, contre l'usage naïf de cette notation.

Les constantes existent. $O(n^2)$ n'interdit pas d'être rapide sur de petites données. Le tri par insertion est en $O(n^2)$, et c'est pourtant lui que les bibliothèques emploient pour trier des morceaux de moins d'une trentaine d'éléments, parce que sur ces tailles sa simplicité l'emporte sur l'élégance asymptotique d'un algorithme plus savant. «Asymptotique» veut dire «quand $n$ devient grand»: si $n$ vaut toujours 12, l'analyse asymptotique ne vous apprend rien.

Le pire cas n'est pas le cas typique. Dire qu'un algorithme est en $O(n^2)$ au pire ne dit pas ce qu'il fait sur vos données. Le tri par insertion en est l'illustration: $O(n^2)$ au pire, et 16 318 comparaisons au lieu de deux millions sur une liste presque triée. Toujours demander: au pire, en moyenne, ou sur mes données réelles?

sorted et list.sort: ce que Python fait à votre place

Deux outils, une différence essentielle

Vous n'écrirez plus jamais de tri. Python en fournit deux formes, et la différence entre elles est la distinction du chapitre 6 entre créer une nouvelle liste et modifier celle qui existe.

• sorted(iterable) renvoie une nouvelle liste triée et laisse l'original intact. Il accepte n'importe quel itérable: une liste, un tuple, une chaîne, les clés d'un dictionnaire.
• liste.sort() trie la liste sur place et ne renvoie rien (None). C'est une méthode de liste, donc elle n'existe que pour les listes.

tableau = [38, 27, 43, 3, 9, 82, 10]

copie_triee = sorted(tableau)
print("sorted    :", copie_triee)
print("original  :", tableau)

tableau.sort()
print("apres sort:", tableau)
print("valeur de retour de sort() :", [38, 27].sort())

sorted    : [3, 9, 10, 27, 38, 43, 82]
original  : [38, 27, 43, 3, 9, 82, 10]
apres sort: [3, 9, 10, 27, 38, 43, 82]
valeur de retour de sort() : None

Cette dernière ligne est la source de l'erreur la plus fréquente de tout ce chapitre. Écrivons-la exprès.

tableau = [38, 27, 43, 3, 9, 82, 10]
tableau = tableau.sort()      # piege: sort() ne renvoie rien
print(tableau[0])

Traceback (most recent call last):
  File "tri.py", line 3, in <module>
    print(tableau[0])
          ~~~~~~~^^^
TypeError: 'NoneType' object is not subscriptable

Relisons ce message ligne à ligne, comme l'annexe B y invite. Traceback (most recent call last) annonce la pile des appels, du plus ancien au plus récent. La ligne suivante donne le fichier et le numéro de ligne, ici 3 — mais la faute est à la ligne 2. Puis le code fautif, souligné par les ~~~^^^ sous l'expression exacte qui a échoué. Enfin le type et le message: TypeError signifie que l'on a appliqué une opération à un objet du mauvais type, et NoneType object is not subscriptable que l'on a écrit quelque_chose[0] sur un objet valant None. La cause réelle: tableau.sort() a trié la liste et renvoyé None, que l'affectation a rangé dans tableau, écrasant la liste triée. La règle est simple: liste.sort() s'écrit seul sur sa ligne, sorted(liste) s'écrit à droite d'un =.

Trier selon un critère: le paramètre key

Les deux formes acceptent deux paramètres nommés: reverse=True pour l'ordre décroissant, et surtout key, qui reçoit une fonction. Python applique cette fonction à chaque élément et trie selon les valeurs obtenues, sans modifier les éléments eux-mêmes.

Reprenons le carnet de notes du cours (dix étudiants fictifs, notes suisses de 1 à 6, moyenne 4,55). Trier un dictionnaire par valeur décroissante s'écrit alors en trois lignes.

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0, "Elena": 4.0,
         "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0, "Ines": 5.0, "Jonas": 4.5}


def la_note(couple):

David   6.0
Farid   5.5
Bruno   5.0
Ines    5.0
Alice   4.5
Gaelle  4.5
Jonas   4.5
Elena   4.0
Chloe   3.5
Hugo    3.0

notes.items() produit les couples (nom, note) du chapitre 7; la_note extrait le second membre de chaque couple; sorted trie selon cette valeur. Observez les ex æquo: Bruno précède Ines à 5,0, et Alice, Gaelle et Jonas se suivent dans cet ordre à 4,5 — c'est-à-dire exactement leur ordre de départ. Le tri de Python est stable (stable sort): il ne permute jamais deux éléments de même clé. C'est une propriété précieuse, car elle permet de trier en deux temps — d'abord par nom, puis par note — et d'obtenir un classement par note où les ex æquo sont par ordre alphabétique.

Sans key, Python compare les éléments directement, ce qui suppose qu'ils soient comparables entre eux:

melange = [3, "9", 10]
print(sorted(melange))

TypeError: '<' not supported between instances of 'str' and 'int'

Le message dit précisément ce qui manque: l'opérateur < n'est pas défini entre une chaîne et un entier. Le tri, quel qu'il soit, ne sait faire qu'une chose — comparer deux éléments — et si cette comparaison n'a pas de sens, il n'y a pas de tri.

Une fonction est une valeur

Regardez de près l'appel sorted(notes.items(), key=la_note, reverse=True). On y écrit la_note sans parenthèses. On n'appelle pas la fonction: on la donne à sorted, qui l'appellera lui-même, une fois par élément, quand il en aura besoin. La fonction chronometre du début du chapitre faisait déjà la même chose avec son paramètre fonction. C'est possible parce qu'en Python une fonction n'est pas seulement un morceau de programme qu'on exécute: c'est aussi un objet, au même titre qu'un nombre ou une liste.

def la_note(couple):
    """Cle de tri: la note d'un couple (nom, note)."""
    return couple[1]


cle = la_note
print(cle(("Alice", 4.5)))
print(la_note)
print(type(la_note))

4.5
<function la_note at 0x1072b82c0>
<class 'function'>

La ligne cle = la_note ne calcule rien: elle colle une deuxième étiquette sur le même objet fonction, exactement comme liste2 = liste1 au chapitre 6. cle(...) appelle donc la_note. Afficher la fonction elle-même donne son nom et son adresse en mémoire — le nombre hexadécimal change d'une exécution à l'autre — et son type est function.

lambda: une fonction sans nom

Écrire une fonction de quatre lignes, docstring comprise, pour dire «prends le second élément du couple», c'est beaucoup. Python offre une forme courte pour les fonctions qui se réduisent à une seule expression:

lambda couple: couple[1]

Le mot-clé lambda, puis les paramètres séparés par des virgules, un deux-points, et une seule expression, dont la valeur est renvoyée. Il n'y a ni nom, ni def, ni return. Cette expression vaut un objet fonction, que l'on peut passer directement à sorted:

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0, "Elena": 4.0,
         "Farid": 5.5, "Gaelle": 4.5, "Hugo": 3.0, "Ines": 5.0, "Jonas": 4.5}

classement = sorted

[('David', 6.0), ('Farid', 5.5), ('Bruno', 5.0)]

C'est le classement de tout à l'heure, sans la fonction la_note. Les deux écritures sont équivalentes: lambda couple: couple[1] fabrique le même objet fonction que le def de la_note, privé de son nom et de sa docstring.

Une lambda ne peut contenir qu'une expression: ni affectation, ni boucle, ni if sur plusieurs lignes, ni return — la valeur de l'expression est le résultat. Le mot return y est d'ailleurs refusé dès la lecture du fichier:

  File "double.py", line 3
    double = lambda x: return 2 * x
                       ^^^^^^
SyntaxError: invalid syntax

Pas de ligne Traceback: comme toute SyntaxError (annexe B), celle-ci est détectée avant que la moindre ligne ne s'exécute. On peut ranger une lambda dans une variable, carre = lambda x: x * x, et l'appeler ensuite, carre(4) donne 16; mais c'est un def déguisé, sans docstring et avec un nom moins lisible dans les traces d'erreur. Le guide de style officiel de Python, PEP 8, le déconseille. Une lambda sert à une seule chose: écrire sur place une petite fonction qu'on passe en argument.

min et max acceptent aussi une clé

Le paramètre key n'appartient pas qu'aux tris. min et max l'acceptent avec le même sens: ils comparent les éléments selon la valeur que la clé leur associe, et renvoient l'élément, pas la valeur de la clé.

print(max(notes.items(), key=lambda couple: couple[1]))
print(min(notes.items(), key=lambda couple: couple[1]))
print(max(notes, key=notes.get))
mots = ["dichotomie", "tri", "insertion", "cout", "selection"]
print(sorted(mots, key=len

('David', 6.0)
('Hugo', 3.0)
David
['tri', 'cout', 'insertion', 'selection', 'dichotomie']
dichotomie
['tri', 'cout', 'insertion', 'selection', 'dichotomie']

Le couple de la meilleure note et celui de la plus basse sont obtenus sans tri et en un seul parcours, ce qui est préférable quand on ne veut qu'un extrême: $n-1$ comparaisons au lieu d'un tri complet. max(notes, key=notes.get) parcourt les clés du dictionnaire et les compare selon la note que renvoie la méthode get — une méthode liée à un objet est elle aussi une valeur qu'on peut passer. Enfin, insertion et selection ont tous deux neuf lettres: sorted(mots, key=len) les laisse dans leur ordre de départ, parce que le tri est stable, et la clé en tuple de la dernière ligne les départagerait par ordre alphabétique s'ils étaient arrivés dans l'autre ordre.

Ce que Python utilise vraiment: Timsort

L'algorithme de tri de CPython s'appelle Timsort, du prénom de Tim Peters qui l'a écrit pour Python en 2002; il a depuis été repris ailleurs, notamment dans la bibliothèque standard de Java. Ce n'est pas un algorithme «pur»: c'est un hybride, conçu pour exploiter l'ordre déjà présent dans les données. Il repère dans la liste les portions déjà croissantes ou décroissantes, appelées runs, trie par insertion les morceaux trop courts — le tri par insertion de ce chapitre, exactement — puis fusionne les portions obtenues deux à deux. Son coût est en $O(n\log n)$ au pire, et il descend à $O(n)$ sur une liste déjà triée.

Cette dernière propriété se mesure, avec la fonction chronometre du début de chapitre, sur une liste de 200 000 entiers pseudo-aléatoires (graine fixée, données fictives).

random.seed(10)
aleatoire = [random.randint(0, 999999) for _ in range(200000)]
deja_trie = sorted(aleatoire)
print(f"sorted sur une liste aleatoire    : {chronometre(sorted, aleatoire):.4f} s")
print(f"sorted sur une liste deja triee   : {chronometre(sorted, deja_trie):.4f} s"

sorted sur une liste aleatoire    : 0.0237 s
sorted sur une liste deja triee   : 0.0010 s

Une vingtaine de fois plus rapide sur des données déjà ordonnées — les trois relances suivantes ont donné des rapports de 24, 17 et 22, tous du même ordre. La promesse «conçu pour exploiter l'ordre existant» n'est donc pas une formule publicitaire, c'est un comportement observable. Nous ne détaillerons pas la fusion ni la façon dont Timsort choisit la taille de ses runs: cela relève du cours «Algorithmes».

Votre tri contre le sien

Reste la question pratique: de combien mon tri est-il moins bon? Mesurons, sur les mêmes 2000 nombres pseudo-aléatoires, avec la fonction chronometre du début de chapitre.

random.seed(10)
donnees = [random.randint(0, 9999) for _ in range(2000)]
t_sel = chronometre(tri_selection, donnees)
t_ins = chronometre(tri_insertion, donnees)
t_py = chronometre(sorted, donnees)
print(f"tri_selection : {t_sel:.4f} s")
print(f"tri_insertion : {t_ins

tri_selection : 0.0576 s
tri_insertion : 0.0660 s
sorted        : 0.000134 s
rapport selection / sorted : 431
les trois donnent le meme resultat : True

Sur cette machine et pour cette taille, sorted a été environ 430 fois plus rapide que notre tri par sélection (les relances ont donné 448 et 430: le rapport est stable à quelques pour cent près). Deux causes se cumulent, et il est important de ne pas les confondre. La première est algorithmique: $O(n\log n)$ contre $O(n^2)$, ce qui pour $n=2000$ vaut déjà un facteur d'environ 90 sur le nombre de comparaisons. La seconde est d'implémentation: Timsort est écrit en C dans l'interpréteur, alors que nos boucles sont interprétées instruction par instruction, ce qui coûte un facteur supplémentaire de l'ordre de plusieurs dizaines. Et le rapport ne fait que croître avec $n$: à 20 000 éléments il serait bien plus grand encore, parce que le facteur algorithmique, lui, augmente avec la taille.

Ce que vous savez faire, et ce qui vient ensuite

Ce chapitre clôt la partie algorithmique du cours, et il vaut la peine de mesurer le chemin parcouru. Vous êtes parti d'une variable et d'un print au chapitre 1. Vous savez maintenant écrire un programme structuré en fonctions, manipuler des chaînes, des listes et des dictionnaires, lire et écrire des fichiers, traiter les erreurs, raisonner récursivement — et, depuis ce chapitre, juger un programme sur autre chose que sa justesse. Vous savez mesurer son temps sans vous mentir, compter ses opérations, distinguer un coût logarithmique d'un coût linéaire ou quadratique, et reconnaître le moment où un algorithme doit être remplacé plutôt qu'optimisé ligne à ligne.

Le chapitre 11 met ces outils au service du calcul scientifique: les tableaux de numpy appliquent à des millions de nombres la leçon de ce chapitre — une boucle écrite en C plutôt qu'interprétée —, et matplotlib en fait des graphiques. Au-delà, trois autres cours prennent le relais, et il est utile de savoir ce que chacun ajoute.

• Le cours «Algorithmes» reprend la notation $O$ pour la définir avec ses quantificateurs, et l'accompagne de $\Omega$ et $\Theta$. Il démontre ce que nous n'avons fait que constater — par exemple qu'aucun tri fondé sur des comparaisons ne peut faire mieux que $O(n\log n)$ dans le pire des cas — et construit les algorithmes qui atteignent cette borne (tri fusion, tri rapide, tas). Il introduit les structures de données qui rendent d'autres opérations rapides: arbres de recherche, tables de hachage, graphes et leurs parcours.
• Le cours «Programmation orientée objet» change l'unité d'organisation du programme. Ici, tout tenait dans des fonctions et des listes; là, les données et les opérations qui leur sont propres sont réunies dans des objets, ce qui permet d'écrire des programmes de dizaines de milliers de lignes sans s'y perdre. Vous en avez déjà croisé les traces: liste.sort() et chaine.upper() sont des méthodes, c'est-à-dire des fonctions attachées à un objet.
• Le cours «Information, calcul et communication» pose les questions en amont du programme: qu'est-ce que l'information et comment la coder, que peut-on calculer en principe, et qu'est-ce qui reste hors de portée de toute machine quel que soit le temps disponible. Il reprend d'ailleurs le tableau [38, 27, 43, 3, 9, 82, 10] de ce chapitre, pour en dire d'autres choses.

Une dernière remarque, qui vaut au-delà de la programmation. Ce chapitre vous a fait mesurer avant d'affirmer: un compteur plutôt qu'une intuition, une sortie de programme plutôt qu'un souvenir, un rapport annoncé avec la machine sur laquelle il a été obtenu. Cette discipline est la même dans toutes les disciplines expérimentales, et c'est peut-être ce que ce cours vous laissera de plus durable.

Synthèse

• Un programme se juge sur sa justesse et sur son coût. Le coût se mesure en secondes avec time.perf_counter — en répétant, en jetant le premier tour et en retenant le minimum — et se compte en opérations élémentaires à l'aide d'un compteur ajouté dans le code. Une durée dépend de la machine, du langage et des données; un nombre de comparaisons ne dépend que de l'algorithme.
• La recherche séquentielle coûte 1 comparaison au mieux, $n$ au pire, $(n+1)/2$ en moyenne: mesuré sur le tableau du cours, 1, 7 et exactement 4,0 comparaisons. La recherche dichotomique sur un tableau trié examine au plus $\lfloor {\log }_{2}n\rfloor +1$ éléments — un par tour de boucle: mesuré, 3 pour 7 éléments, 10 pour mille, 20 pour un million. Un texte qui compte les coupes en deux plutôt que les éléments examinés écrit $\lceil {\log }_{2}n\rceil$, soit une unité de moins sur les puissances de deux: vérifiez toujours ce que compte un coût logarithmique. Son invariant est «si la cible est là, son indice est entre et »; sur un tableau non trié elle renvoie silencieusement un résultat faux.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

def compter_recherche(tableau, cible):
    """Recherche sequentielle renvoyant (indice, nombre de comparaisons)."""
    comparaisons = 0
    for i in range(len(tableau)):
        comparaisons = comparaisons + 1
        if

def ecart_naif(nombres):
    """Compare toutes les paires: renvoie (ecart, comparaisons)."""
    comparaisons = 0
    ecart = 0
    for i in range(len(nombres)):
        for j in range(i +

print(tri_insertion_compte([5, 2, 9

notes = {"Alice": 4.5, "Bruno": 5.0, "Chloe": 3.5, "David": 6.0, "Elena": 4.0,
         "Farid"

def nombre_voyelles(mot):
    """Nombre de voyelles (sans accents) d'un mot."""
    return len([c for c in mot if c in "aeiouy"])


mots = [

Références

• Downey, Think Python, 2ᵉ édition, O'Reilly — chapitre 10 («Lists») pour la recherche et le tri, et l'annexe B («Analysis of Algorithms») pour l'ordre de grandeur des coûts.
• Guttag, Introduction to Computation and Programming Using Python, MIT Press — les chapitres consacrés à la complexité et aux algorithmes de recherche et de tri, avec le même choix de compter les opérations plutôt que les secondes.
• Swinnen, Apprendre à programmer avec Python 3, Eyrolles — le chapitre sur les listes et leurs méthodes, pour sort, sorted et key.
• Documentation officielle Python, The Python Standard Library, section «time» pour perf_counter, et Sorting Techniques (HOWTO) pour key, reverse et la stabilité du tri.
• Documentation officielle Python, Built-in Functions, entrées sorted, min et max, et Data Structures du tutoriel officiel pour list.sort.