Algorithmique en prépa : tri, recherche et complexité

En prépa, l'algorithmique n'est pas un cours de programmation de plus. C'est un changement de regard : on ne demande plus seulement « est-ce que mon programme marche ? », mais « combien coûte-t-il quand les données grossissent ? ». Deux algorithmes qui donnent le même résultat peuvent avoir des performances séparées par un facteur mille sur un gros tableau. Savoir écrire un algorithme correct et savoir en estimer le coût, ce sont les deux réflexes que le programme d'informatique pour tous, et plus encore l'option informatique de MPSI, cherchent à installer.

Cet article te donne le socle : ce qu'est un algorithme, la recherche séquentielle et la recherche dichotomique sur un tableau trié, les deux tris au programme (par insertion et par sélection) avec une mention des tris fusion et rapide, la notion de complexité en temps par comptage d'opérations, la distinction meilleur cas / pire cas, et la comparaison des coûts. Tout est illustré par du code Python commenté et trois analyses corrigées, dont une comparaison de deux algorithmes. Nos profs Hadamard, anciens de MPSI, de MP2I et de MPSI option info passés par l'X, l'ENS et CentraleSupélec, ont tous programmé et donné des khôlles d'informatique : ils te montrent ce que le jury et les DS attendent vraiment.

Qu'est-ce qu'un algorithme

Un algorithme est une suite finie et ordonnée d'instructions élémentaires qui, à partir de données en entrée, produit un résultat en sortie et se termine. C'est une recette : elle décrit quoi faire, étape par étape, indépendamment du langage. Le même algorithme de tri peut s'écrire en Python, en C ou en pseudo-code au tableau.

Trois exigences sont attendues en prépa pour qu'un objet mérite le nom d'algorithme, et deux qualités le rendent utile :

• Finitude. Le nombre d'étapes est fini : l'algorithme se termine sur toute entrée valide (pas de boucle infinie).
• Déterminisme. Chaque étape est définie sans ambiguïté : pour une même entrée, on obtient toujours la même sortie.
• Effectivité. Chaque instruction est élémentaire, réalisable en un temps fini (une comparaison, une affectation, une addition).
• Correction. L'algorithme renvoie bien le résultat attendu. On la justifie souvent par un invariant de boucle.
• Efficacité. Il utilise raisonnablement le temps et la mémoire. C'est tout l'objet de la complexité, au cœur de cet article.

La recherche séquentielle

Premier problème classique : chercher si une valeur cible figure dans un tableau, et à quel indice. La méthode la plus naturelle est la recherche séquentielle (ou linéaire) : on parcourt le tableau case par case, du début à la fin, jusqu'à trouver la cible ou atteindre la fin.

def recherche_sequentielle(tab, cible):
    for i in range(len(tab)):        # on parcourt chaque indice
        if tab[i] == cible:
            return i                 # trouvé : on renvoie l'indice
    return -1                        # fin du tableau sans trouver : absent

Elle a un grand avantage : elle fonctionne sur n'importe quel tableau, trié ou non. Son défaut est le coût. Notons $n$ la taille du tableau et comptons les comparaisons tab[i] == cible :

• Meilleur cas : la cible est en première position, une seule comparaison, coût $O(1)$.
• Pire cas : la cible est en dernière position, ou absente, il faut $n$ comparaisons, coût $O(n)$.
• Cas moyen : si la cible est présente à une position quelconque, environ $n/2$ comparaisons, ce qui reste $O(n)$.

On retient donc que la recherche séquentielle est un algorithme linéaire, en $O(n)$ : doubler la taille du tableau double le temps de calcul dans le pire cas.

La recherche dichotomique sur un tableau trié

Si le tableau est déjà trié, on peut faire infiniment mieux. C'est le réflexe du dictionnaire papier : pour trouver un mot, on n'ouvre jamais à la première page, on ouvre au milieu, puis on recommence sur la moitié qui contient le mot. C'est la recherche dichotomique : on compare la cible à l'élément du milieu de l'intervalle, et selon le résultat on élimine la moitié où elle ne peut pas se trouver.

def recherche_dichotomique(tab, cible):
    g, d = 0, len(tab) - 1           # bornes de l'intervalle de recherche
    while g <= d:
        m = (g + d) // 2             # indice du milieu (division entière)
        if tab[m] == cible:
            return m                 # trouvé
        elif tab[m] < cible:
            g = m + 1                # la cible est dans la moitié droite
        else:
            d = m - 1                # la cible est dans la moitié gauche
    return -1                        # intervalle vide : absent

L'analyse est spectaculaire. À chaque tour de boucle, la taille de l'intervalle $[g, d]$ passe d'environ $k$ à $k/2$. Partant de $n$, après $p$ étapes il reste environ $n / 2^p$ éléments. La recherche s'arrête quand l'intervalle est réduit à un élément, c'est-à-dire lorsque $n / 2^p \approx 1$, soit $2^p \approx n$, donc $p \approx \log_2 n$. Le coût dans le pire cas est :

Le prix à payer, c'est le tri préalable : la dichotomie n'est correcte que sur un tableau trié. Si l'on ne fait qu'une seule recherche, trier d'abord ne vaut pas le coup. Si l'on fait des milliers de recherches sur les mêmes données, trier une fois puis dichotomiser à chaque requête est le bon choix. C'est exactement le genre de compromis que le jury adore creuser à l'oral.

Les algorithmes de tri

Trier un tableau, c'est ranger ses éléments dans l'ordre croissant. Deux tris sont au programme d'informatique pour tous, tous deux fondés sur des boucles imbriquées et tous deux de complexité $O(n^2)$ dans le pire cas : le tri par insertion et le tri par sélection.

Le tri par insertion

C'est le tri du joueur de cartes : on prend les éléments un par un et on insère chacun à sa place parmi ceux déjà triés à sa gauche, en décalant vers la droite les plus grands.

def tri_insertion(tab):
    for i in range(1, len(tab)):     # tab[0..i-1] est déjà trié
        cle = tab[i]                 # élément à insérer
        j = i - 1
        while j >= 0 and tab[j] > cle:
            tab[j + 1] = tab[j]      # on décale vers la droite
            j = j - 1
        tab[j + 1] = cle             # on place la clé à sa position
    return tab

Comptons les comparaisons tab[j] > cle. Dans le pire cas, un tableau trié à l'envers, chaque nouvel élément doit remonter tout le tableau déjà trié : la boucle interne fait $1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2}$ comparaisons, soit $O(n^2)$. Dans le meilleur cas, un tableau déjà trié, la condition tab[j] > cle est fausse dès le premier test : on fait une seule comparaison par élément, soit $n-1$ au total, c'est-à-dire $O(n)$. C'est la grande force du tri par insertion : il est très rapide sur des données presque triées.

Le tri par sélection

Autre stratégie : à chaque étape, on cherche le minimum de la partie non encore triée et on le place à sa position définitive par un échange.

def tri_selection(tab):
    n = len(tab)
    for i in range(n - 1):
        i_min = i                    # indice du plus petit trouvé
        for j in range(i + 1, n):    # on cherche le min du reste
            if tab[j] < tab[i_min]:
                i_min = j
        tab[i], tab[i_min] = tab[i_min], tab[i]   # échange
    return tab

Ici le comptage ne dépend pas du contenu : la boucle interne effectue toujours $(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}$ comparaisons, quel que soit le tableau. Le tri par sélection est donc en $O(n^2)$ dans tous les cas, meilleur comme pire. Il ne profite jamais d'un tableau déjà trié, contrairement au tri par insertion. En revanche il fait peu d'échanges (au plus $n-1$), ce qui peut compter quand déplacer un élément coûte cher.

Les tris efficaces : fusion et rapide

Peut-on faire mieux que $O(n^2)$ ? Oui, grâce au principe « diviser pour régner » : on coupe le problème en sous-problèmes plus petits, on les résout, puis on recombine. Deux tris célèbres l'appliquent.

• Tri fusion. On coupe le tableau en deux moitiés, on trie chacune récursivement, puis on fusionne les deux moitiés triées. Sa complexité est $O(n \log n)$ dans tous les cas.
• Tri rapide. On choisit un pivot, on place à sa gauche les plus petits et à sa droite les plus grands, puis on recommence sur chaque côté. En moyenne $O(n \log n)$, mais $O(n^2)$ dans un pire cas défavorable (pivot mal choisi).

Ces deux tris ne sont pas exigés en détail en informatique pour tous, mais leur existence et leur ordre de grandeur $O(n \log n)$ doivent être connus. Ils sont écrits, démontrés et comparés dans l'option informatique de MPSI et dans la filière MP2I.

La complexité en temps

La complexité en temps d'un algorithme mesure le nombre d'opérations élémentaires qu'il effectue en fonction de la taille $n$ des données. On ne mesure pas un temps en secondes, qui dépendrait de la machine et du langage : on compte des opérations (comparaisons, affectations, additions), ce qui donne une mesure objective et transposable.

Comme le nombre exact d'opérations est fastidieux, on ne garde que l'ordre de grandeur dominant quand $n$ devient grand, exprimé avec la notation $O$ (« grand O »). Dire qu'un algorithme est en $O(n^2)$ signifie que, pour $n$ assez grand, son nombre d'opérations est majoré par une constante fois $n^2$. On néglige les constantes et les termes de plus bas degré : $\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}$ est un $O(n^2)$. La notation $O$ mérite un article à elle seule, on la détaille dans notre guide de la complexité et de la notation $O$.

Point crucial : la complexité peut dépendre non seulement de la taille des données, mais de leur contenu. On distingue alors :

• Le meilleur cas : la configuration d'entrée la plus favorable (tri par insertion sur un tableau déjà trié, $O(n)$).
• Le pire cas : la configuration la plus défavorable (tri par insertion sur un tableau trié à l'envers, $O(n^2)$). C'est la borne la plus utile car elle garantit une performance quoi qu'il arrive.
• Le cas moyen : la moyenne sur toutes les entrées possibles, souvent plus délicate à calculer.

Comparer les complexités

Voici le récapitulatif des algorithmes vus, avec leur complexité en temps. C'est le tableau à savoir reconstituer de tête.

Pour sentir l'écart, comparons le nombre d'opérations pour quelques tailles. La croissance de $n^2$ est écrasante face à $n \log n$, elle-même bien au-dessus de $\log n$.

Trois analyses corrigées

Analyse 1 · Compter les comparaisons d'une recherche séquentielle

Énoncé. On applique recherche_sequentielle au tableau tab = [4, 9, 2, 7, 5]. Combien de comparaisons tab[i] == cible sont effectuées pour cible = 4, pour cible = 5, et pour cible = 8 ? En déduire le meilleur et le pire cas pour un tableau de taille $n$.

Solution. On parcourt de l'indice $0$ jusqu'à trouver la cible.

• cible = 4 : trouvée en position $0$, 1 comparaison. C'est le meilleur cas.
• cible = 5 : trouvée en position $4$ (dernière), 5 comparaisons.
• cible = 8 : absente, on teste les $5$ cases, 5 comparaisons.

Pour un tableau de taille $n$, le meilleur cas est la cible en tête ($1$ comparaison, $O(1)$) et le pire cas est la cible en dernière position ou absente ($n$ comparaisons, $O(n)$). La recherche séquentielle est linéaire.

Analyse 2 · Dérouler une recherche dichotomique

Énoncé. On applique recherche_dichotomique au tableau trié tab = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (10 éléments, indices $0$ à $9$) avec cible = 23. Dérouler les étapes et compter les comparaisons.

Solution. On suit les bornes $g$ et $d$ et le milieu $m = (g+d) // 2$.

La cible est trouvée à l'indice $5$ en 3 comparaisons d'égalité, là où la recherche séquentielle en aurait fait $6$. Le pire cas ici est $\lceil \log_2(10) \rceil = 4$ étapes : l'intervalle passe de $10$ à $5$, à $2$ ou $3$, puis à $1$. On vérifie bien le coût $O(\log n)$.

Analyse 3 · Comparer tri par insertion et tri par sélection

Énoncé. On veut trier un tableau déjà trié de taille $n = 6$, par exemple [1, 2, 3, 4, 5, 6]. Combien de comparaisons chaque tri effectue-t-il ? Lequel est le plus efficace sur ce cas, et pourquoi ?

Solution. On compte les comparaisons de chaque algorithme sur un tableau déjà croissant.

Tri par insertion. Pour chaque élément d'indice $i$ (de $1$ à $5$), la condition tab[j] > cle est fausse dès le premier test, car l'élément précédent est déjà plus petit. On fait donc 1 comparaison par élément :

Tri par sélection. Il ignore l'ordre initial : à chaque étape $i$ il parcourt tout le reste du tableau pour trouver le minimum. Le nombre de comparaisons est fixe :

Ce qu'il faut retenir

• Un algorithme est une suite finie, déterministe et effective d'instructions ; on le juge sur sa correction et sur son coût.
• Recherche séquentielle : parcours case par case, $O(n)$, marche sur tout tableau.
• Recherche dichotomique : sur un tableau trié, on divise l'intervalle par deux, $O(\log n)$.
• Tri par insertion : $O(n^2)$ au pire, mais $O(n)$ sur un tableau presque trié.
• Tri par sélection : toujours $\frac{n(n-1)}{2}$ comparaisons, $O(n^2)$ dans tous les cas.
• Tris fusion et rapide : « diviser pour régner », $O(n \log n)$ (en moyenne pour le rapide).
• Complexité en temps : on compte les opérations selon $n$, on garde l'ordre dominant en notation $O$, on distingue meilleur et pire cas.

Ces algorithmes forment le socle du programme d'informatique de première année. La suite naturelle est l'étude des structures de données (listes, piles, files, arbres), qui déterminent elles aussi la complexité des opérations, et l'approfondissement de la notation $O$ et de l'analyse de complexité. Pour aller plus loin en algorithmique et en preuve de programmes, l'option informatique de MPSI et la filière MP2I sont les voies dédiées.