SunuLab
Notre savoir
SunuCode/ Parcours
CoursAvancé14 min de lecture

Algorithmes fondamentaux

Chercher et trier — les deux problèmes de base, et la question du coût d'un algorithme

§1.Un algorithme, c'est une méthode

Un algorithme est une suite d'étapes qui résout un problème à coup sûr, en un nombre fini d'opérations. La notion est bien plus ancienne que les ordinateurs : poser une division, c'est appliquer un algorithme.

Deux problèmes reviennent partout : CHERCHER une valeur dans une collection, et TRIER une collection. Presque tout le reste s'y ramène ou en dépend.

Ce chapitre a un second objectif, plus important encore que les méthodes elles-mêmes : te faire poser la question du COÛT. Deux programmes qui donnent le même résultat ne se valent pas forcément.

§2.Chercher : la méthode évidente

La recherche LINÉAIRE consiste à regarder chaque élément l'un après l'autre jusqu'à trouver. C'est ce que tu fais en cherchant tes clés : tu inspectes les endroits un par un.

Elle a une grande qualité : elle marche toujours, y compris sur une collection en désordre. Et un défaut : sur un million d'éléments, il peut falloir un million de comparaisons.

Recherche linéaire
python
def recherche_lineaire(liste, cible):
    for i in range(len(liste)):
        if liste[i] == cible:
            return i
    return -1
 
print(recherche_lineaire([7, 2, 9, 4], 9))
print(recherche_lineaire([7, 2, 9, 4], 5))
Résultat : 2 -1

On renvoie l'INDEX plutôt que True : c'est plus informatif, et -1 signale l'absence. Le return dans la boucle sort dès qu'on a trouvé — inutile de continuer.

§4.Chercher dans une collection TRIÉE : la dichotomie

Si la collection est triée, on peut faire radicalement mieux. C'est ce que tu fais avec un dictionnaire papier : tu ne commences pas à la page 1, tu ouvres au milieu et tu décides d'aller à gauche ou à droite.

À chaque comparaison, on élimine la MOITIÉ des candidats restants. Sur un million d'éléments, vingt comparaisons suffisent — contre un million pour la recherche linéaire.

C'est le premier exemple frappant qu'un meilleur algorithme bat une machine plus rapide. Un téléphone qui fait une dichotomie écrase un supercalculateur qui fait une recherche linéaire.

Recherche dichotomique
python
def dichotomie(liste, cible):
    gauche = 0
    droite = len(liste) - 1
    etapes = 0
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        etapes = etapes + 1
        if liste[milieu] == cible:
            print("trouvé en", etapes, "étapes")
            return milieu
        if liste[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1
 
triee = list(range(0, 2000, 2))    # 1000 éléments
print(dichotomie(triee, 1998))
Résultat : trouvé en 10 étapes 999

Mille éléments, dix étapes. Et si on passait à un million d'éléments, il n'en faudrait que vingt : chaque doublement de la taille ne coûte qu'UNE comparaison de plus.

Compare les deux méthodes
Chargement de l'éditeur Python…

§8.Trier : trois méthodes, deux familles

Python sait trier tout seul avec sorted(). Reconstruire les tris à la main n'a donc pas d'intérêt pratique — il en a un pédagogique : ce sont les exemples les plus clairs pour comprendre qu'une même tâche admet des méthodes de coûts très différents.

Les deux premiers tris, à bulles et par sélection, sont dits QUADRATIQUES : doubler la taille des données quadruple le travail. Le troisième, le tri fusion, appartient à une famille bien plus efficace.

Tri à bulles

On compare chaque élément à son voisin et on échange s'ils sont dans le désordre. Les grandes valeurs « remontent ».

python
def tri_bulles(liste):
    t = list(liste)
    for i in range(len(t)):
        for j in range(len(t) - 1 - i):
            if t[j] > t[j + 1]:
                t[j], t[j + 1] = t[j + 1], t[j]
    return t
 
print(tri_bulles([5, 2, 9, 1, 7]))
Résultat : [1, 2, 5, 7, 9]

Le -1-i est important : après chaque passe, la plus grande valeur restante est à sa place définitive, inutile de la recomparer.

Tri par sélection

On cherche le minimum du reste et on le met à sa place définitive. Puis on recommence.

python
def tri_selection(liste):
    t = list(liste)
    for i in range(len(t)):
        mini = i
        for j in range(i + 1, len(t)):
            if t[j] < t[mini]:
                mini = j
        t[i], t[mini] = t[mini], t[i]
    return t
 
print(tri_selection([5, 2, 9, 1, 7]))
Résultat : [1, 2, 5, 7, 9]

Même coût que le tri à bulles, mais bien moins d'échanges : un seul par tour, au lieu d'un à chaque comparaison défavorable.

Tri fusion : diviser pour régner

On coupe la liste en deux, on trie chaque moitié, et on fusionne. La fusion de deux listes déjà triées est facile — c'est là qu'est l'astuce.

python
def fusionner(a, b):
    resultat = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            resultat.append(a[i])
            i = i + 1
        else:
            resultat.append(b[j])
            j = j + 1
    return resultat + a[i:] + b[j:]
 
 
def tri_fusion(liste):
    if len(liste) <= 1:
        return list(liste)
    m = len(liste) // 2
    return fusionner(tri_fusion(liste[:m]), tri_fusion(liste[m:]))
 
 
print(tri_fusion([5, 2, 9, 1, 7, 3]))
Résultat : [1, 2, 3, 5, 7, 9]

La fonction s'appelle elle-même sur des morceaux plus petits : c'est de la RÉCURSION, le sujet du dernier chapitre. Le coût passe de n² à n log n — sur dix mille éléments, c'est environ sept cents fois moins de travail.

§12.Le coût, en ordre de grandeur

AlgorithmeCoûtSur 1 000 élémentsSur 1 000 000
Recherche linéairen1 000 étapes1 000 000 étapes
Recherche dichotomiquelog n10 étapes20 étapes
Tri à bulles / sélectionn²1 000 000 opérations10¹² opérations
Tri fusionn log n10 000 opérations20 000 000 opérations

Ce sont des ordres de grandeur, pas des mesures. Ce qui compte est la FORME de la croissance, pas la valeur exacte : c'est elle qui décide si ton programme tiendra quand les données grossiront.

§13.Pourquoi cette question est la bonne

Sur dix éléments, tous ces algorithmes se valent — la différence est invisible. Sur un million, l'un répond instantanément et l'autre ne finit jamais.

L'erreur classique du débutant est de juger un programme sur le jeu de données minuscule avec lequel il l'a testé. La bonne question n'est pas « est-ce que ça marche ? » mais « qu'est-ce qui se passe si les données sont mille fois plus grandes ? ».

En pratique, tu utiliseras sorted() — implémenté en C, remarquablement optimisé. Mais savoir ce qu'il fait, et pourquoi il ne fait pas un tri à bulles, change la façon dont tu écris tout le reste.

Vérifie qu'ils donnent le même résultat

Trois méthodes différentes, un seul résultat. C'est ça, un algorithme correct.

Chargement de l'éditeur Python…

À retenir

  • Recherche linéaire : simple, marche toujours, coût proportionnel à la taille.
  • Recherche dichotomique : exige une liste TRIÉE, élimine la moitié des candidats à chaque étape.
  • Sur une liste non triée, la dichotomie ne plante pas — elle répond faux. C'est pire.
  • Tris à bulles et par sélection : quadratiques, doubler les données quadruple le travail.
  • Tri fusion : diviser pour régner, n log n — incomparablement meilleur à grande échelle.
  • La bonne question n'est pas « est-ce que ça marche » mais « et si les données étaient mille fois plus grandes ».
  • Tester l'appartenance : instantané dans un ensemble ou un dictionnaire, coûteux dans une liste.
Mots-clésalgorithmerecherchedichotomietricomplexitébullessélectionfusion