Tri, recherche et parcours¶

Trier, chercher et parcourir sont les opérations les plus fréquentes en informatique — les comprendre en profondeur, c'est comprendre comment fonctionnent les bases de données, les compilateurs et les moteurs de recherche.

Tris par comparaison¶

Un tri par comparaison détermine l'ordre en comparant des paires d'éléments. La théorie de l'information prouve que tout tri par comparaison est Ω(n log n) dans le pire cas : l'arbre de décision sur n! feuilles (ordres possibles) a une hauteur minimale de log₂(n!) ≈ n log n. Les algorithmes optimaux atteignent exactement cette borne.

Quicksort¶

Conçu par Tony Hoare en 1959, quicksort est l'algorithme de tri le plus utilisé en pratique malgre un pire cas O(n²). Sa performance moyenne O(n log n) avec de petites constantes et une excellente localité cache en font le choix dominant.

Principe : partition autour d'un pivot

1. Choisir un pivot (élément du tableau)
2. Rearranges le tableau : éléments < pivot à gauche, éléments > pivot à droite
3. Appliquer recursivement sur les deux sous-tableaux

def quicksort(arr: list, lo: int, hi: int) -> None:
    if lo < hi:
        pivot_idx = partition(arr, lo, hi)
        quicksort(arr, lo, pivot_idx - 1)
        quicksort(arr, pivot_idx + 1, hi)

def partition(arr: list, lo: int, hi: int) -> int:
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

Choix du pivot : le pivot le plus naive (premier ou dernier élément) degenere en O(n²) sur un tableau déjà trie. Solutions :

• Median-of-three : choisir la mediane du premier, milieu et dernier élément — pratique dans la plupart des implémentations
• Pivot aléatoire : choisir uniformement au hasard — garantit O(n log n) en esperance pour toute entree
• Introselect : STL C++ utilisé introsort (quicksort + heapsort comme fallback quand la recursion dépassé 2 log n)

Tri in-place : O(log n) d'espace de pile en moyenne. Stable ? Non — les échanges peuvent changer l'ordre relatif d'éléments egaux.

Mergesort¶

Conçu par John von Neumann en 1945. Paradigme divide & conquer : diviser en deux moities, trier chacune recursivement, fusionner les deux sous-tableaux tries.

def mergesort(arr: list) -> list:
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    gauche = mergesort(arr[:mid])
    droite = mergesort(arr[mid:])
    return fusionner(gauche, droite)

def fusionner(gauche: list, droite: list) -> list:
    resultat = []
    i = j = 0
    while i < len(gauche) and j < len(droite):
        if gauche[i] <= droite[j]:
            resultat.append(gauche[i])
            i += 1
        else:
            resultat.append(droite[j])
            j += 1
    resultat.extend(gauche[i:])
    resultat.extend(droite[j:])
    return resultat

Propriétés :

• O(n log n) garanti dans tous les cas — pas de degeneration possible
• Stable : les éléments egaux conservent leur ordre relatif (propriété clé pour les tris secondaires)
• O(n) espace auxiliaire — le tableau temporaire de fusion est l'inconvénient principal
• Excellent pour les listes chaînées (pas besoin de la copie auxiliaire)
• Adapté au tri externe (fichiers trop grands pour la mémoire) : mergesort sur des blocs, fusion de blocs

Heapsort¶

Tri en utilisant un tas max. Construire le tas (O(n) par heapify de Floyd), puis extraire le maximum n fois (n × O(log n) = O(n log n)).

Propriétés :

• O(n log n) garanti dans tous les cas, comme mergesort
• O(1) espace auxiliaire — tri en place, comme quicksort
• Non stable
• Mauvaise localité cache en pratique : le "sift down" saute partout dans le tableau. Quicksort avec median-of-three est souvent 2-3x plus rapide sur des données réelles malgre les mêmes bornes asymptotiques.

Utilité pratique : heapsort sert de fallback dans introsort (STL C++) pour garantir O(n log n) dans le pire cas de quicksort.

Comparatif des tris par comparaison¶

Tris non-comparatifs : quand O(n) est possible¶

Si les éléments ne sont pas compares mais traites directement (entiers dans un intervalle connu), la borne Ω(n log n) ne s'applique plus. On peut trier en O(n).

Counting sort¶

Compter les occurrences de chaque valeur, puis reconstruire le tableau trie.

def counting_sort(arr: list, max_val: int) -> list:
    compte = [0] * (max_val + 1)
    for x in arr:
        compte[x] += 1
    resultat = []
    for val, nb in enumerate(compte):
        resultat.extend([val] * nb)
    return resultat

Complexité : O(n + k) temps et espace, ou k est la plage des valeurs. Si k = O(n), c'est O(n). Si k >> n (valeurs très dispersees), la mémoire devient prohibitive.

Quand l'utiliser : âges (0-150), notes (0-100), codes ASCII, comptages. Pas applicable aux nombres flottants ou aux grands entiers.

Radix sort¶

Trier par chiffres successifs (du moins significatif au plus significatif). Utilisé counting sort comme sous-routine stable à chaque passe.

Exemple : trier [170, 45, 75, 90, 802, 24, 2, 66]
Passe 1 (unites) : [170, 90, 802, 2, 24, 45, 75, 66]
Passe 2 (dizaines) : [802, 2, 24, 45, 66, 170, 75, 90]
Passe 3 (centaines) : [2, 24, 45, 66, 75, 90, 170, 802]

Complexité : O(d × (n + k)) ou d est le nombre de chiffres et k la base (souvent 10 ou 256). Pour des entiers de 32 bits en base 256 : 4 passes, O(4(n + 256)) = O(n). En pratique, radix sort bat quicksort pour des tableaux de plusieurs millions d'entiers.

Stabilité et adaptativite : Timsort¶

Timsort a été conçu par Tim Peters en 2002 pour Python, puis adopte par Java (depuis Java 7, Arrays.sort sur les objets) et Android. C'est l'algorithme de tri le plus utilise aujourd'hui pour les données générales.

Principe : identifier des "runs" (sous-sequences déjà triees croissantes ou decroissantes) dans le tableau, les étendre jusqu'à une taille minimale par insertion sort, puis les fusionner par mergesort.

Propriétés :

• Adaptatif : O(n) sur des données presque triees (détecté les runs naturels), O(n log n) dans le pire cas
• Stable : comme mergesort
• Pratique : les données réelles contiennent souvent des sequences déjà ordonnées (fichiers de logs, listes chronologiques, sorties de bases de données)
• O(n) espace auxiliaire dans le pire cas, mais souvent beaucoup moins

Recherche : séquentielle, dichotomique, interpolation¶

Recherche séquentielle¶

Parcourir le tableau élément par élément jusqu'à trouver la cible. O(n) dans le pire cas, O(1) dans le meilleur (premier élément). Aucune hypothèse sur le tableau.

Quand c'est optimal : pour un tableau non trie, la recherche séquentielle est optimale — il est impossible de faire mieux sans information supplémentaire. Sur de très petits tableaux (n < 16), la recherche séquentielle bat souvent la dichotomique grâce à la localité cache.

Recherche dichotomique¶

Sur un tableau trie, comparer avec l'élément median et réduire la recherche à la moitie inférieure ou supérieure. Diviser par 2 à chaque étape : O(log n).

def dichotomique(arr: list, cible) -> int:
    """Retourne l'indice de cible dans arr trie, ou -1."""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # Evite le debordement entier
        if arr[mid] == cible:
            return mid
        elif arr[mid] < cible:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Invariant de boucle : à chaque iteration, si cible est dans arr, elle est dans arr[lo..hi]. L'invariant est maintenu par les affectations. Il se termine car hi - lo decroit strictement. La correction suit de l'invariant.

Les bugs classiques : utiliser (lo + hi) // 2 (débordement possible en C/Java pour n > 2³⁰), condition lo < hi au lieu de lo <= hi (manque le cas de l'élément unique), ou mal placer le + 1 dans lo = mid + 1.

Variantes :

• bisect.bisect_left(arr, x) — premier indice i tel que arr[i] >= x (borne inférieure)
• bisect.bisect_right(arr, x) — premier indice i tel que arr[i] > x (borne supérieure)
• Utiles pour les insertions dans un tableau trie et les requêtes d'intervalle

Recherche par interpolation¶

Sur des données uniformement distribuées, estimer la position de la cible plutôt que de toujours couper en deux :

pos = lo + (cible - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo])

Complexité : O(log log n) pour des distributions uniformes, O(n) dans le pire cas (distribution degeneree). Utile pour des tableaux d'entiers ou de flottants avec distribution connue. Rarement utilisé en pratique car la robustesse de la dichotomique est préférée.

Parcours de graphes : BFS et DFS¶

Un graphe G = (V, E) est un ensemble de sommets et d'aretes. Les deux algorithmes de parcours fondamentaux explorent tous les sommets atteignables depuis un sommet source.

BFS — Breadth-First Search (parcours en largeur)¶

Parcourir par niveaux : d'abord tous les voisins directs, puis les voisins des voisins, etc. Utilise une file.

from collections import deque

def bfs(graphe: dict, source) -> dict:
    """Retourne les distances minimales depuis source."""
    distance = {source: 0}
    file = deque([source])
    while file:
        sommet = file.popleft()
        for voisin in graphe[sommet]:
            if voisin not in distance:
                distance[voisin] = distance[sommet] + 1
                file.append(voisin)
    return distance

Complexité : O(V + E) — chaque sommet et chaque arete sont traites au plus une fois.

Propriétés :

• Trouve le plus court chemin (en nombre d'aretes) dans un graphe non pondere
• Garantit de visiter les sommets par ordre croissant de distance depuis la source
• O(V) espace pour la file et les distances

Cas d'usage :

• Plus court chemin dans un labyrinthe ou un graphe non pondere
• Composantes connexes
• Vérification de bipartisme (colorier alternativement en 2 couleurs)
• Parcours de pages web (crawlers)
• Trouver les amis "a deux degrés" (réseaux sociaux)

DFS — Depth-First Search (parcours en profondeur)¶

Parcourir aussi loin que possible avant de revenir en arriere. Utilise une pile (ou la pile d'appels de la recursion).

def dfs(graphe: dict, source, visite: set = None) -> None:
    if visite is None:
        visite = set()
    visite.add(source)
    for voisin in graphe[source]:
        if voisin not in visite:
            dfs(graphe, voisin, visite)

Complexité : O(V + E).

Propriétés :

• Ne garantit pas le plus court chemin
• Utile pour l'exploration exhaustive, le backtracking
• Classifie les aretes en aretes d'arbre, aretes retour (back edges), aretes avant, aretes croisees
• Une back edge indique un cycle dans un graphe orienté

Cas d'usage :

• Détection de cycles (présence d'une back edge en DFS)
• Tri topologique
• Composantes fortement connexes (algorithme de Tarjan, Kosaraju)
• Backtracking (n-reines, sudoku, génération de labyrinthes)
• Parcours d'arbres d'expression (compilateurs)

Tri topologique¶

Ordonner les sommets d'un DAG (graphe orienté acyclique) tel que pour toute arete (u → v), u apparait avant v dans l'ordre. Si le graphe contient un cycle, le tri topologique est impossible.

Algorithme par DFS (Kahn alternatif avec file est aussi classique) :

def tri_topologique(graphe: dict) -> list:
    visite = set()
    ordre = []

    def dfs(sommet):
        visite.add(sommet)
        for voisin in graphe.get(sommet, []):
            if voisin not in visite:
                dfs(voisin)
        ordre.append(sommet)  # Ajouter apres traitement des descendants

    for sommet in graphe:
        if sommet not in visite:
            dfs(sommet)

    return ordre[::-1]  # Inverser : les sources en premier

Complexité : O(V + E).

Applications :

• Ordonnancement de migrations de schéma (migration B dépend de migration A)
• Ordre d'évaluation des cellules dans un tableur
• Compilation : ordre de linkage des modules
• Ordre d'installation des paquets avec dépendances (apt, npm)

Applications : cycles dans les dépendances, ordonnancement¶

Détection de cycles dans les dépendances¶

Un système de gestion de paquets doit détecter les dépendances circulaires avant d'essayer de les installer. Exemple : paquet A dépend de B, B dépend de C, C dépend de A — cycle impossible a résoudre.

def detecter_cycle(graphe: dict) -> bool:
    """True si le DAG oriente contient un cycle."""
    BLANC, GRIS, NOIR = 0, 1, 2
    couleur = {s: BLANC for s in graphe}

    def dfs(s) -> bool:
        couleur[s] = GRIS  # En cours de traitement
        for voisin in graphe.get(s, []):
            if couleur[voisin] == GRIS:  # Back edge = cycle
                return True
            if couleur[voisin] == BLANC and dfs(voisin):
                return True
        couleur[s] = NOIR  # Termine
        return False

    return any(dfs(s) for s in graphe if couleur[s] == BLANC)

Les couleurs (blanc/gris/noir) correspondent aux états non visite / en cours / termine du DFS. Une arete vers un sommet GRIS est une back edge — preuve d'un cycle.

Ordonnancement de migrations de base de données¶

Les migrations de schéma SQL ont souvent des dépendances : la migration add_foreign_key_orders_users doit s'exécuter après create_table_users ET create_table_orders. Le graphe de dépendances est un DAG — le tri topologique donne l'ordre d'exécution correct.

Si deux migrations sont indépendantes (pas de chemin entre elles dans le DAG), elles peuvent être exécutées en parallèle — optimisation directe pour les CI/CD pipelines.

Arbre de décision : quel algorithme de tri choisir ?¶

flowchart TD
    A["Donner un tableau a trier"] --> B{"Les elements sont-ils des entiers
    dans une plage connue ?"}

    B -- Oui --> C{"La plage k est-elle
    comparable a n ?"}
    C -- "Oui, k = O(n)" --> D["Counting sort
    O(n + k), stable"]
    C -- "Non, k >> n" --> E{"Multi-passes sur chiffres
    possible ?"}
    E -- Oui --> F["Radix sort
    O(d(n + k)), stable"]
    E -- Non --> G

    B -- Non --> G{"Les donnees sont-elles
    presque deja triees ?"}
    G -- Oui --> H["Timsort ou Tri insertion
    O(n) sur quasi-trie"]
    G -- Non --> I{"Un tri stable est-il
    necessaire ?"}

    I -- Oui --> J["Mergesort ou Timsort
    O(n log n), O(n) espace"]
    I -- Non --> K{"Contrainte memoire
    stricte O(1) ?"}

    K -- Oui --> L["Heapsort
    O(n log n), in-place, non stable"]
    K -- Non --> M["Quicksort avec pivot median-of-three
    O(n log n) moy, rapide en pratique"]