06 — Les tris linéaires : comptage et radix

Ce que tu vas apprendre

• Pourquoi O(n log n) est une barrière pour les tris par comparaison
• Comment le tri par comptage trie en O(n) sans comparer
• Le tri radix pour les grands nombres et les chaînes
• Les conditions strictes qui rendent ces tris applicables

Prérequis

• 05 — Tri par tas

Tous les tris vus jusqu'ici comparent des éléments deux à deux. On peut démontrer qu'aucun tri par comparaison ne peut faire mieux que O(n log n) dans le pire cas : c'est une limite théorique, pas un défaut d'implémentation. Pourtant, certains tris atteignent O(n). Le truc : ils ne comparent pas les éléments, ils exploitent directement leur valeur. En échange, ils ne marchent que sous des conditions précises.

La barrière des comparaisons

L'intuition de la limite O(n log n) : un tri par comparaison doit pouvoir distinguer toutes les permutations possibles de n éléments, et il y en a n!. Chaque comparaison donne un bit d'information (plus petit, ou plus grand). Il faut donc au moins log₂(n!) comparaisons, ce qui vaut environ n log n. Tant qu'on se limite à comparer, on ne peut pas descendre en dessous. Pour aller plus vite, il faut utiliser une autre information que la comparaison : la valeur elle-même.

Le tri par comptage

Le tri par comptage s'applique quand les éléments sont des entiers dans une plage connue et pas trop grande (par exemple, des notes de 0 à 20, des âges, des codes). Au lieu de comparer, on compte combien de fois chaque valeur apparaît, puis on reconstruit le tableau trié à partir de ces comptes.

pythondef tri_comptage(arr: list[int], valeur_max: int) -> list[int]:
    comptes = [0] * (valeur_max + 1)
    for x in arr:
        comptes[x] += 1          # on compte chaque valeur : O(n)
    result = []
    for valeur, n in enumerate(comptes):
        result.extend([valeur] * n)  # on reconstruit dans l'ordre : O(n + k)
    return result

Si n est le nombre d'éléments et k l'étendue des valeurs, la complexité est O(n + k). Quand k est de l'ordre de n ou plus petit, c'est du O(n) : on a battu la barrière. Le tri par comptage est aussi stable dans sa version complète (celle qui calcule des positions cumulées), ce qui le rend utilisable comme brique du tri radix.

La condition est stricte : ça ne marche que pour des entiers (ou des clés mappables sur des entiers) dans une plage raisonnable. Trier un million de valeurs entre 0 et 2 milliards par comptage demanderait un tableau de comptes de 2 milliards de cases : inutilisable. La mémoire O(k) est le facteur limitant.

Le tri radix

Le tri radix lève la limite de plage en triant les nombres chiffre par chiffre. On trie d'abord selon le chiffre des unités, puis des dizaines, puis des centaines, en utilisant à chaque étape un tri stable (souvent le tri par comptage sur un seul chiffre, donc sur une plage de 0 à 9).

pythondef tri_radix(arr: list[int]) -> list[int]:
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:           # une passe par chiffre
        arr = tri_comptage_par_chiffre(arr, exp)
        exp *= 10
    return arr

def tri_comptage_par_chiffre(arr: list[int], exp: int) -> list[int]:
    comptes = [0] * 10
    for x in arr:
        comptes[(x // exp) % 10] += 1
    for i in range(1, 10):
        comptes[i] += comptes[i - 1]    # positions cumulées (stabilité)
    result = [0] * len(arr)
    for x in reversed(arr):             # parcours inverse = stable
        chiffre = (x // exp) % 10
        comptes[chiffre] -= 1
        result[comptes[chiffre]] = x
    return result

Si les nombres ont d chiffres, on fait d passes, chacune en O(n). La complexité est O(d × n). Quand d est petit et constant (des entiers bornés, des chaînes de longueur fixe), c'est du O(n). Le tri radix s'applique aussi aux chaînes de caractères, en triant caractère par caractère.

Quand les utiliser

Ces tris ne remplacent pas les tris généralistes. Tu ne les utiliseras pas pour trier des objets quelconques avec un comparateur arbitraire. Mais quand tes clés sont des entiers bornés (identifiants, timestamps tronqués, scores, codes postaux), ils peuvent être nettement plus rapides que le sort() standard. C'est un outil de niche, à sortir quand le profil des données s'y prête.

L'article suivant clôt la série en revenant au monde réel : ce que font vraiment sort() en JavaScript et sorted() en Python, et pourquoi la réponse est Timsort, un hybride qui combine plusieurs des tris vus dans cette série.

Sources

• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapitre 8 "Sorting in Linear Time". MIT Press.
• Seward, H. H. (1954). Première description du tri par comptage et radix, rapportée par Knuth (1998). TAOCP Vol. 3. Addison-Wesley.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 5.1 "String Sorts". Addison-Wesley.