Tri, recherche et coût des programmes

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))
print(somme_formule(1000))
print(somme_boucle(1000) == somme_formule(1000))

500500
500500
True

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

boucle  : 0.03870400000596419 s
formule : 2.2080494090914726e-06 s

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)

Exemple 10.1 · Les deux sommes, mesurées proprement

Appliquons chronometre aux deux fonctions du début, pour $n = 1 0^{6}$ .

t_boucle = chronometre(somme_boucle, 1000000)
t_formule = chronometre(somme_formule, 1000000)
print(f"boucle  : {t_boucle:.6f} s")
print(f"formule : {t_formule:.9f} s")
print(f"rapport : {t_boucle / t_formule:.0f}")

boucle  : 0.031418 s
formule : 0.000000125 s
rapport : 251401

Relancé, le programme a donné 0,029040 s et 0,000000125 s, soit un rapport de 232 265: la variation est tombée de 150 % à 8 %. La mesure est maintenant assez stable pour être citée. On retiendra: sur cette machine, pour un million de termes, la boucle est de l'ordre de 200 000 fois plus lente que la formule. Pas «251 401 fois»: les deux derniers chiffres n'ont aucune signification.

Notez aussi le format {t_boucle:.6f} des f-strings du chapitre 5: il impose six décimales, sans quoi Python afficherait l'écriture scientifique et la comparaison visuelle serait pénible.

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, 1000000]:
    resultat, additions = somme_comptee(n)
    print(f"n = {n:>7} : somme = {resultat:>14} , additions = {additions}")

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

	Chronométrer (secondes)	Compter (opérations)
Dépend de la machine	oui	non
Dépend du langage	oui	non
Reproductible	approximativement	exactement
Prévisible avant exécution	non	oui
Répond à «est-ce assez rapide pour mon utilisateur?»	oui	non
Répond à «que se passera-t-il si $n$ est mille fois plus grand?»	mal	oui

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

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

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} , {comparaisons} comparaisons")

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

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

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:
            droite = milieu - 1
    return -1

Exemple 10.2 · La dichotomie sur le tableau du cours, pas à pas

Cherchons la valeur 10 dans le tableau trié, en instrumentant la boucle pour qu'elle raconte ce qu'elle fait à chaque tour.

trie = [3, 9, 10, 27, 38, 43, 82]
cible = 10
gauche, droite, etape = 0, len(trie) - 1, 0
while gauche <= droite:
    etape += 1
    milieu = (gauche + droite) // 2
    print(f"etape {etape}: gauche={gauche} droite={droite} milieu={milieu} "
          f"tableau[milieu]={trie[milieu]} intervalle={trie[gauche:droite+1]}")
    if trie[milieu] == cible:
        print("  trouve")
        break
    elif trie[milieu] < cible:
        gauche = milieu + 1
        print("  trop petit -> on garde la moitie droite")
    else:
        droite = milieu - 1
        print("  trop grand -> on garde la moitie gauche")

etape 1: gauche=0 droite=6 milieu=3 tableau[milieu]=27 intervalle=[3, 9, 10, 27, 38, 43, 82]
  trop grand -> on garde la moitie gauche
etape 2: gauche=0 droite=2 milieu=1 tableau[milieu]=9 intervalle=[3, 9, 10]
  trop petit -> on garde la moitie droite
etape 3: gauche=2 droite=2 milieu=2 tableau[milieu]=10 intervalle=[10]
  trouve

Sept candidats, puis trois, puis un. Trois éléments examinés au lieu des sept (ici six, puisque 10 est à l'indice 2) qu'aurait demandés la recherche séquentielle.

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

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 dichotomique_recursive(tableau, cible, gauche, milieu - 1)

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

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] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1, comparaisons

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))
    maxi = 0
    for cible in trie:
        _, c = recherche_dichotomique_comptee(trie, cible)
        if c > maxi:
            maxi = c
    print(f"{n:>7} {maxi:>10} {math.floor(math.log2(n)) + 1:>10} {n:>15}")

      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

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 != i:
            t[i], t[indice_min] = t[indice_min], t[i]
    return t

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 t[j] < t[indice_min]:
            indice_min = j
    if indice_min != i:
        t[i], t[indice_min] = t[indice_min], t[i]
    print(f"passe {i} : min = {t[i]} (indice {indice_min}) -> {t}")

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]

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 = j - 1
        t[j + 1] = valeur                   # on depose la valeur
    return t

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:
        t[j + 1] = t[j]
        j = j - 1
    t[j + 1] = valeur
    print(f"i = {i} (valeur {valeur:>2}) -> {t}")

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]

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 + 1
            if t[j] < t[indice_min]:
                indice_min = j
        if indice_min != i:
            t[i], t[indice_min] = t[indice_min], t[i]
            echanges = echanges + 1
    return t, comparaisons, echanges

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
            if t[j] <= valeur:
                break
            t[j + 1] = t[j]
            decalages = decalages + 1
            j = j - 1
        t[j + 1] = valeur
    return t, comparaisons, decalages

Exemple 10.3 · Les deux tris sur le tableau du cours, comptés

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

resultat, comparaisons, echanges = tri_selection_compte(tableau)
print("selection :", resultat)
print(f"  {comparaisons} comparaisons, {echanges} echanges")

resultat, comparaisons, decalages = tri_insertion_compte(tableau)
print("insertion :", resultat)
print(f"  {comparaisons} comparaisons, {decalages} decalages")

selection : [3, 9, 10, 27, 38, 43, 82]
  21 comparaisons, 5 echanges
insertion : [3, 9, 10, 27, 38, 43, 82]
  15 comparaisons, 11 decalages

Les deux tris donnent évidemment le même tableau trié. Mais ils n'ont pas fait le même travail.

Le tri par sélection a fait exactement 21 comparaisons, et ce nombre n'est pas un hasard: la passe 0 en fait 6, la passe 1 en fait 5, et ainsi de suite jusqu'à 1, donc

C_{s \overset{e}{ˊ} lection} (n) = (n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2}, (10.3)

soit $7 \times 6/2 = 21$ pour $n = 7$ . Ce nombre ne dépend pas du tout du contenu du tableau: les deux boucles sont des for dont les bornes ne dépendent que de $n$ , et aucun break ne les interrompt. En revanche les échanges, eux, dépendent des données: il y en a eu 5 sur 6 passes, la passe 4 s'en étant dispensée.

Le tri par insertion a fait 15 comparaisons, soit 6 de moins, et 11 décalages. Son nombre de comparaisons dépend des données, puisque la boucle while s'arrête dès qu'elle rencontre un élément plus petit. Sur ce tableau particulier, il est plus économe en comparaisons et plus dépensier en écritures.

Exemple 10.4 · Le même tableau dans trois ordres, compté

Un tri se juge sur trois situations: des données déjà triées, des données en ordre inverse, et des données quelconques. Mesurons-les toutes les trois.

cas = {
    "deja trie      ": [3, 9, 10, 27, 38, 43, 82],
    "ordre inverse  ": [82, 43, 38, 27, 10, 9, 3],
    "tableau du cours": [38, 27, 43, 3, 9, 82, 10],
}
for nom, tableau in cas.items():
    _, c_sel, e_sel = tri_selection_compte(tableau)
    _, c_ins, d_ins = tri_insertion_compte(tableau)
    print(f"{nom} selection {c_sel:>3} comp. / {e_sel} ech."
          f"   insertion {c_ins:>3} comp. / {d_ins:>2} dec.")

deja trie       selection  21 comp. / 0 ech.   insertion   6 comp. /  0 dec.
ordre inverse   selection  21 comp. / 3 ech.   insertion  21 comp. / 21 dec.
tableau du cours selection  21 comp. / 5 ech.   insertion  15 comp. / 11 dec.

Lisez la colonne du tri par sélection: 21, 21, 21. Rien ne le fait dévier. Il ne tire aucun profit d'un tableau déjà trié; il refait consciencieusement toutes ses comparaisons pour découvrir à chaque passe que le minimum était déjà en place. Son seul gain est de n'effectuer aucun échange.

Lisez maintenant celle du tri par insertion: 6, 21, 15.

Sur un tableau déjà trié, il fait $n - 1 = 6$ comparaisons et aucun décalage: une seule comparaison par élément suffit à constater qu'il est à sa place. C'est son cas favorable, et il est proportionnel à $n$ , pas à $n^{2}$ .
Sur un tableau en ordre inverse, chaque nouvel élément doit remonter jusqu'au début: $1 + 2 + \dots + 6 = 21$ comparaisons et 21 décalages. C'est son cas défavorable, et il rejoint exactement la formule (10.3).

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)

for nom, donnees in [("aleatoire   ", aleatoire), ("presque trie", presque_triee)]:
    _, c_sel, _ = tri_selection_compte(donnees)
    _, c_ins, _ = tri_insertion_compte(donnees)
    print(f"{nom} : selection {c_sel:>8} comparaisons, insertion {c_ins:>8}")

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

Algorithme	Comparaisons (pire cas)	Pour $n = 1000$
Recherche dichotomique	$⌊ lo g_{2} n ⌋ + 1$	10
Recherche séquentielle	$n$	1 000
Tri par insertion, cas favorable	$n - 1$	999
Tri par insertion, cas moyen	environ $n^{2} /4$	environ 250 000
Tri par sélection, tri par insertion au pire	$n (n - 1) /2$	499 500

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 f"{t / precedent:.1f}"
    print(f"n = {n:>4} : {comparaisons:>9} comparaisons, {t:.4f} s, rapport {rapport}")
    precedent = t

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

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

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

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):
    """Cle de tri: la note d'un couple (nom, note)."""
    return couple[1]


classement = sorted(notes.items(), key=la_note, reverse=True)
for nom, note in classement:
    print(f"{nom:<7} {note}")

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

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

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

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

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:.4f} s")
print(f"sorted        : {t_py:.6f} s")
print(f"rapport selection / sorted : {t_sel / t_py:.0f}")
print(f"les trois donnent le meme resultat :",
      tri_selection(donnees) == tri_insertion(donnees) == sorted(donnees))

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

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 $⌊ lo g_{2} n ⌋ + 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 $⌈ lo g_{2} n ⌉$ , 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 gauche et droite»; sur un tableau non trié elle renvoie silencieusement un résultat faux.
Le tri par sélection fait toujours $n (n - 1) /2$ comparaisons, quel que soit le tableau: 21 sur le tableau du cours, dans les trois cas testés. Le tri par insertion en fait $n - 1$ sur des données déjà triées, $n (n - 1) /2$ en ordre inverse, environ $n^{2} /4$ en moyenne: mesuré, 6, 21 et 15 sur le tableau du cours, et 16 318 contre 1 999 000 sur une liste de 2000 éléments presque triée.
La notation $O$ dit «croît comme», aux constantes près: $O (lo g n)$ pour la dichotomie, $O (n)$ pour la recherche séquentielle, $O (n^{2})$ pour les deux tris de ce chapitre. Multiplier $n$ par 10 multiplie un coût linéaire par 10, un coût quadratique par 100, et ajoute trois ou quatre unités à un coût logarithmique — vérifié en mesurant le quadruplement exact des comparaisons quand la taille double.
sorted(liste) renvoie une nouvelle liste triée, liste.sort() trie sur place et renvoie None; confondre les deux produit un TypeError: 'NoneType' object is not subscriptable. Le paramètre key reçoit une fonction qui donne le critère de tri, et le tri de Python est stable.
Python utilise Timsort, un hybride conçu pour exploiter l'ordre déjà présent: mesuré, une vingtaine de fois plus rapide sur une liste déjà triée que sur une liste aléatoire de même taille, et environ 430 fois plus rapide que notre tri par sélection sur 2000 éléments. N'écrivez pas votre propre tri autrement que comme exercice.

Exercice 10.1 · Compter les comparaisons d'une recherche

Écrivez une fonction compter_recherche(tableau, cible) qui effectue une recherche séquentielle et renvoie le couple formé de l'indice trouvé (ou −1) et du nombre de comparaisons effectuées. Testez-la sur le tableau du cours avec les cibles 43, 82 et 7, et vérifiez à la main que les comptages sont corrects.

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 tableau[i] == cible:
            return i, comparaisons
    return -1, comparaisons


tableau = [38, 27, 43, 3, 9, 82, 10]
for cible in [43, 82, 7]:
    print(cible, compter_recherche(tableau, cible))

43 (2, 3)
82 (5, 6)
7 (-1, 7)

Vérification à la main: 43 est à l'indice 2, donc on a comparé 38, 27 puis 43, soit 3 comparaisons — l'indice plus un. 82 est à l'indice 5: 6 comparaisons. 7 est absent: l'algorithme parcourt les 7 éléments et renvoie −1 après 7 comparaisons, ce qui est le pire cas.

Le point important est le placement de comparaisons = comparaisons + 1: il doit être avant le if, car la comparaison a lieu que le test réussisse ou non. Placé après, le compteur oublierait la comparaison décisive et renverrait toujours un de moins.

Exercice 10.2 · Le plus grand écart

Écrivez deux fonctions qui, à partir d'une liste de nombres, calculent l'écart entre le plus grand et le plus petit. La première, ecart_naif, compare toutes les paires possibles avec deux boucles imbriquées. La seconde, ecart_direct, fait un seul parcours. Comptez les comparaisons de chacune sur le tableau du cours, et dites comment chaque coût croît avec la taille.

Solution

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 + 1, len(nombres)):
            comparaisons = comparaisons + 1
            if abs(nombres[i] - nombres[j]) > ecart:
                ecart = abs(nombres[i] - nombres[j])
    return ecart, comparaisons

def ecart_direct(nombres):
    """Un seul parcours: renvoie (ecart, comparaisons)."""
    comparaisons = 0
    mini = nombres[0]
    maxi = nombres[0]
    for valeur in nombres[1:]:
        comparaisons = comparaisons + 2
        if valeur < mini:
            mini = valeur
        if valeur > maxi:
            maxi =

naif   : (79, 21)
direct : (79, 12)

Les deux trouvent 79, l'écart entre 82 et 3. La version naïve compare les $7 \times 6/2 = 21$ paires, c'est-à-dire autant que le tri par sélection: son coût est en $O (n^{2})$ . La version directe fait deux comparaisons par élément après le premier, soit $2 (n - 1) = 12$ : son coût est en $O (n)$ .

Pour $n = 1000$ , cela ferait 499 500 comparaisons contre 1998, soit 250 fois moins; pour $n = 1 0^{6}$ , le rapport atteindrait 250 000. Le gain ne vient pas d'un code plus astucieux ligne à ligne, mais d'un changement d'algorithme: on a remplacé «examiner toutes les paires» par «retenir deux extrêmes au passage».

Exercice 10.3 · Insertion, pas à pas

Sans exécuter de programme, écrivez à la main les six lignes de la trace du tri par insertion sur la liste [5, 2, 9, 1, 7], puis comptez les comparaisons et les décalages. Vérifiez ensuite avec tri_insertion_compte.

Solution

À la main, en insérant chaque élément dans la partie déjà triée à sa gauche:

Tour	Valeur insérée	Liste après le tour	Comparaisons	Décalages
départ	—	5, 2, 9, 1, 7	—	—
i = 1	2	2, 5, 9, 1, 7	1	1
i = 2	9	2, 5, 9, 1, 7	1	0
i = 3	1	1, 2, 5, 9, 7	3	3
i = 4	7	1, 2, 5, 7, 9	2	1
total			7	5

Détail du tour i = 3: la valeur 1 est comparée à 9 (décalage), à 5 (décalage), à 2 (décalage), puis j vaut −1 et la boucle s'arrête sans autre comparaison — d'où 3 comparaisons et 3 décalages. Au tour i = 4, la valeur 7 est comparée à 9 (décalage) puis à 5 qui est plus petit: la boucle s'arrête, 2 comparaisons et 1 décalage.

Vérification:

print(tri_insertion_compte([5, 2, 9, 1, 7]))

([1, 2, 5, 7, 9], 7, 5)

Les comptages faits à la main et ceux du compteur coïncident. À titre de comparaison, le tri par sélection aurait fait $5 \times 4/2 = 10$ comparaisons sur la même liste, quelle qu'elle soit.

Exercice 10.4 · Trier le carnet de notes de plusieurs façons

À partir du dictionnaire notes du cours, produisez successivement: la liste des noms par ordre alphabétique; la liste des couples triés par note croissante; la liste des couples triés par note décroissante puis, à note égale, par ordre alphabétique. Utilisez sorted et le paramètre key, sans écrire de tri.

Solution

Il faut deux fonctions de clé: l'une renvoie la note, l'autre renvoie un couple pour trier sur deux critères à la fois.

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):
    """Cle de tri: la note d'un couple (nom, note)."""
    return couple[1]


def note_puis_nom(couple):
    """Cle de tri: note decroissante d'abord, nom croissant ensuite."""
    return (-couple[1], couple[0])

print("alphabetique       :", sorted(notes))
print("note croissante    :", sorted(notes.items(), key=la_note)[:3])
print("note decr. puis nom:", sorted(notes.items(), key=note_puis_nom)[:4])

alphabetique       : ['Alice', 'Bruno', 'Chloe', 'David', 'Elena', 'Farid', 'Gaelle', 'Hugo', 'Ines', 'Jonas']
note croissante    : [('Hugo', 3.0), ('Chloe', 3.5), ('Elena', 4.0)]
note decr. puis nom: [('David', 6.0), ('Farid', 5.5), ('Bruno', 5.0), ('Ines', 5.0)]

Trois points à retenir. D'abord, sorted(notes) trie les clés du dictionnaire, puisque parcourir un dictionnaire donne ses clés (chapitre 7); pour trier les couples il faut notes.items().

Ensuite, la fonction note_puis_nom renvoie un tuple. Python compare deux tuples élément par élément: il compare d'abord -couple[1], et le signe moins renverse l'ordre sur un nombre, ce qui donne les notes décroissantes; en cas d'égalité il compare couple[0], donc les noms par ordre alphabétique croissant. C'est la manière standard de trier sur plusieurs critères d'un seul appel.

Enfin, seules les trois ou quatre premières entrées sont affichées, au moyen d'une tranche [:3] du chapitre 5, pour que la sortie tienne sur une ligne. À 5,0, Bruno passe avant Ines: ici ce n'est pas la stabilité du tri qui l'impose, mais bien le second critère du tuple.

Exercice 10.5 · À partir de quelle taille le tri est-il rentable?

On dispose d'un tableau de $n$ éléments dans lequel on doit effectuer $r$ recherches. Deux stratégies s'offrent: $r$ recherches séquentielles, ou un tri par sélection suivi de $r$ recherches dichotomiques. Écrivez un programme qui, pour $n = 1000$ , détermine par simulation la plus petite valeur de $r$ à partir de laquelle la seconde stratégie fait moins de comparaisons. Commentez le résultat.

Solution

Le raisonnement se fait entièrement avec les formules du chapitre, mais le programme les vérifie par des compteurs réels.

import math

n = 1000
cout_sequentiel = n                        # pire cas d'une recherche
cout_tri = n * (n - 1) // 2                # tri par selection
cout_dicho = math.floor(math.log2(n)) + 1  # pire cas d'une dichotomie

r = 1
while r * cout_sequentiel <= cout_tri + r * cout_dicho:
    r = r

cout d'une recherche sequentielle : 1000
cout du tri                       : 499500
cout d'une recherche dichotomique : 10
seuil de rentabilite r            : 505

Le seuil se retrouve par le calcul: il faut $r \cdot 1000 > 499500 + 10 r$ , soit $990 r > 499500$ , soit $r > 504, 5$ , donc $r = 505$ .

Interprétation. Trier coûte cher — ici l'équivalent de 500 recherches séquentielles — mais ce coût est payé une seule fois, alors que l'économie se répète à chaque recherche. En dessous de 505 recherches, mieux vaut ne pas trier; au-delà, le tri est remboursé et tout le reste est du gain. Et le seuil s'effondre si l'on trie avec sorted au lieu du tri par sélection: le coût du tri passe de l'ordre de $n^{2} /2$ à l'ordre de $n lo g_{2} n \approx 10000$ , et la rentabilité est atteinte après une dizaine de recherches seulement.

C'est la raison d'être des index d'une base de données: on paie le tri une fois, à l'écriture, pour rendre logarithmique chacune des millions de lectures qui suivront.

Objectifs du chapitre

Deux programmes, une même réponse

Mesurer: le temps d'exécution

Le chronomètre de Python

Chronométrer honnêtement

Compter: les opérations élémentaires

La recherche séquentielle

Le problème et l'algorithme

Les trois cas

La recherche dichotomique

L'idée: exploiter l'ordre

La trace, étape par étape

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

La version récursive

Le logarithme, mesuré

Trier: deux algorithmes élémentaires

Le tri par sélection

Le tri par insertion

Les compteurs

Cas favorable et cas défavorable, mesurés

Premières notions de complexité

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

La notation O, prudemment

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

Deux outils, une différence essentielle

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

Ce que Python utilise vraiment: Timsort

Votre tri contre le sien

Ce que vous savez faire, et ce qui vient ensuite

Synthèse

Le coût d'une recherche séquentielle

Le coût du tri, une fois pour toutes

Le coût d'une recherche dichotomique

Au bout de combien de temps le tri est-il rentable?

Exercices

Références

Objectifs du chapitre

Deux programmes, une même réponse

Mesurer: le temps d'exécution

Le chronomètre de Python

Chronométrer honnêtement

Compter: les opérations élémentaires

La recherche séquentielle

Le problème et l'algorithme

Les trois cas

La recherche dichotomique

L'idée: exploiter l'ordre

La trace, étape par étape

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

La version récursive

Le logarithme, mesuré

Trier: deux algorithmes élémentaires

Le tri par sélection

Le tri par insertion

Les compteurs

Cas favorable et cas défavorable, mesurés

Premières notions de complexité

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

La notation O, prudemment

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

Deux outils, une différence essentielle

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

Ce que Python utilise vraiment: Timsort

Votre tri contre le sien

Ce que vous savez faire, et ce qui vient ensuite

Synthèse

Le coût d'une recherche séquentielle

Le coût du tri, une fois pour toutes

Le coût d'une recherche dichotomique

Au bout de combien de temps le tri est-il rentable?

Exercices

Références

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

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