Combien d'étapes ? Tris, dichotomie, tuples et dictionnaires en Python

Ton téléphone retrouve un contact parmi huit cents en un éclair, ton appli de musique trie ta bibliothèque d'un geste. Derrière, deux questions : combien d'opérations coûte un algorithme quand les données grossissent, et comment ranger les données pour les retrouver vite ? Le coût d'un tri ou d'une recherche se compte en comparaisons, selon la taille n des données : comment grandit-il quand n double ?

Le tri par sélection

On cherche le plus petit élément, on l'échange avec la première case, puis on recommence sur le reste du tableau.

def tri_selection(t):
 n = len(t)
 for i in range(n - 1):
 i_min = i
 for j in range(i + 1, n):
 if t[j] < t[i_min]:
 i_min = j
 t[i], t[i_min] = t[i_min], t[i]

Sur [7, 3, 9, 1], les trois passages donnent [1, 3, 9, 7], puis la même liste (3 est déjà en place), puis [1, 3, 7, 9], en 3 + 2 + 1 = 6 comparaisons. Pour n éléments, (n − 1) + (n − 2) + … + 1 = n × (n − 1)2, quel que soit l'ordre de départ : 4 950 pour 100 éléments, 499 500 pour 1 000. Quand n double, le coût est multiplié par environ 4 : il est quadratique.

Il est correct grâce à un invariant de boucle : après le passage i, les cases 0 à i contiennent les i + 1 plus petits éléments, triés. Il termine, car ses boucles for font un nombre fini de tours.

Le tri par insertion

C'est le geste du joueur de cartes : chaque élément glisse vers la gauche jusqu'à sa place.

def tri_insertion(t):
 for i in range(1, len(t)):
 cle = t[i]
 j = i - 1
 while j >= 0 and t[j] > cle:
 t[j + 1] = t[j]
 j = j - 1
 t[j + 1] = cle

Invariant : avant de traiter la case i, les cases 0 à i − 1 sont triées. Dans le pire cas, un tableau rangé à l'envers, chaque élément remonte jusqu'au début : encore n × (n − 1)2 comparaisons, coût quadratique. Dans le meilleur cas, un tableau déjà trié, une seule comparaison par élément suffit : n − 1 en tout.

La recherche dichotomique

Dans un tableau trié, on regarde le milieu et on élimine la moitié où la valeur ne peut pas être.

def recherche_dicho(t, x):
 debut, fin = 0, len(t) - 1
 while debut <= fin:
 milieu = (debut + fin) // 2
 if t[milieu] == x:
 return milieu
 elif t[milieu] < x:
 debut = milieu + 1
 else:
 fin = milieu - 1
 return -1

Cherchons 23 dans t = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Tour 1 : milieu = 4, t[4] = 16 < 23, donc debut = 5. Tour 2 : milieu = 7, t[7] = 56 > 23, donc fin = 6. Tour 3 : milieu = 5, t[5] = 23, la fonction renvoie 5. Pour 40, absent, elle renvoie −1 après quatre tours.

La boucle termine, car l'entier fin − debut diminue strictement à chaque tour : c'est un variant de boucle. Comme la zone est coupée en deux à chaque tour, 20 tours suffisent pour un million d'éléments (2²⁰ = 1 048 576), contre un million de lectures case par case : le coût est logarithmique.

Bien ranger ses données

• Un tuple groupe quelques valeurs, point = (48.85, 2.35), lues par indice (point[0]) mais impossibles à modifier : il est immuable. Idéal pour renvoyer plusieurs valeurs.
• Un p-uplet nommé donne un nom à chaque champ : e.moyenne est plus lisible que e[2].
• Un dictionnaire associe des clés à des valeurs : stock = {"stylo": 12}, puis stock["gomme"] = 3 ajoute une clé. Le test "stylo" in stock reste très rapide même avec des millions de clés, contrairement à une liste.

from collections import namedtuple

Eleve = namedtuple("Eleve", ["nom", "classe", "moyenne"])
inscrits = [Eleve("Inès", "1G2", 14.5), Eleve("Noam", "1G1", 12.0),
 Eleve("Jade", "1G2", 16.25)]


def extremes(liste):
 moyennes = [e.moyenne for e in liste]
 return max(moyennes), min(moyennes)


haut, bas = extremes(inscrits)
effectifs = {}
for e in inscrits:
 effectifs[e.classe] = effectifs.get(e.classe, 0) + 1
print(haut, bas, effectifs)

Ce programme affiche 16.25 12.0 {'1G2': 2, '1G1': 1}. La ligne haut, bas = extremes(inscrits) déballe le tuple renvoyé, et effectifs.get(e.classe, 0) renvoie 0 tant que la clé n'existe pas.

À retenir

• Le coût d'un algorithme compte ses opérations, ici les comparaisons, selon la taille n des données.
• Sélection et insertion : coût quadratique, n × (n − 1)2 comparaisons au pire ; l'insertion n'en fait que n − 1 sur un tableau trié.
• La recherche dichotomique exige un tableau trié et coupe la zone en deux à chaque tour : coût logarithmique.
• Tuple : immuable, accès par indice ; p-uplet nommé : accès par nom de champ ; dictionnaire : couples clé-valeur, accès rapide par la clé.

★ Pour aller plus loin

En Terminale, le tri fusion coupe le tableau en deux, trie chaque moitié puis fusionne : environ n × log₂(n) comparaisons, soit 20 millions pour un million d'éléments, contre 500 milliards pour le tri par sélection.

La fonction sorted de Python utilise Timsort (Tim Peters, 2002), qui fusionne les morceaux déjà triés. Les dictionnaires, eux, reposent sur une table de hachage : un calcul sur la clé donne directement la case de la valeur.

Sources pour creuser

• Numérique et sciences informatiques 1re : 30 leçons avec exercices corrigés, Balabonski, Conchon, Filliâtre et Nguyen (Ellipses).
• Le temps des algorithmes, Serge Abiteboul et Gilles Dowek (Le Pommier).
• La chaîne YouTube Science4All de Lê Nguyên Hoang ; cherche aussi « tri par insertion animation ».
• docs.python.org/fr, chapitre « Structures de données » du tutoriel ; france-ioi.org pour s'entraîner ; le programme de NSI sur eduscol.education.fr.