Tris sans comparaison et sort() de Python

Tout algorithme de tri qui détermine l'ordre uniquement au moyen de comparaisons entre éléments nécessite au moins Ω(n log n) comparaisons dans le pire cas. Cela se démontre par l'argument de l'arbre de décision : trier n éléments nécessite de distinguer les n! ordres possibles. Un arbre de décision binaire (chaque nœud correspondant à une comparaison) doit comporter au moins log₂(n!) ≈ n log₂(n) niveaux. Pour contourner cette borne, nous avons besoin d'informations supplémentaires sur les éléments, par exemple qu'il s'agit d'entiers bornés.

Le tri par comptage fonctionne en comptant la fréquence de chaque valeur, puis en reconstruisant le tableau trié à partir de ces comptes. Il faut connaître à l'avance l'intervalle [0, k) des valeurs. Complexité temporelle : O(n + k) ; complexité spatiale : O(k). Lorsque k est petit par rapport à n (par exemple pour trier des âges compris entre 0 et 120 ou des chiffres isolés), le tri par comptage surpasse tous les tris par comparaison. Lorsque k est grand, le coût en espace O(k) le rend peu pratique.

Pour un tri par comptage stable (important lors du tri d’objets selon une clé), calculez les comptes cumulés afin que cum[v] donne la position de départ de la valeur v dans la sortie. Parcourez le tableau d’entrée de droite à gauche, en plaçant chaque élément à la position cum[key] - 1, puis décrémentez cette position. Vous obtenez ainsi un tri stable : les éléments ayant la même clé apparaissent dans le même ordre relatif que dans l’entrée.

Le tri par base trie les entiers chiffre par chiffre, du chiffre le moins significatif (LSD) au plus significatif (MSD), en utilisant un tri stable (comme le tri par comptage) à chaque position. Après d passes (une par chiffre), le tableau est entièrement trié. Complexité temporelle : O(d × (n + k)), où d = nombre de chiffres et k = base (généralement 10). Pour n entiers bornés par W, d = log_k(W), soit O(n log_k(W)) au total.

Le tri par compartiments répartit les éléments dans un nombre fixe de compartiments selon leur intervalle de valeurs, trie chaque compartiment (avec un tri par insertion pour les petits compartiments), puis les concatène. Pour des données uniformément réparties dans [0, 1), n compartiments donnent un temps moyen en O(n). Complexité temporelle : O(n + k) en moyenne, O(n²) dans le pire cas (tous les éléments dans un seul compartiment). Cette méthode est particulièrement utile lorsque la distribution des données est connue et approximativement uniforme.

Les fonctions sorted() et list.sort() de Python utilisent Timsort, conçu par Tim Peters en 2002. Timsort est un hybride du tri fusion et du tri par insertion. Il recherche les « séquences naturelles » (des sous-séquences déjà triées) et utilise le tri par insertion pour construire des séquences allant jusqu’à 64 éléments. Il fusionne ensuite les séquences avec le tri fusion, en appliquant plusieurs optimisations : le saut par blocs (pour ignorer plusieurs éléments d’un coup lorsqu’une séquence est dominante) et l’empilement des longueurs de séquences.

list.sort() trie sur place, renvoie None et ne fonctionne que sur les listes. sorted(iterable) fonctionne avec tout objet itérable (tuples, générateurs, dictionnaires) et renvoie une nouvelle liste. Les deux acceptent les paramètres key et reverse. Une erreur courante consiste à affecter le résultat de lst.sort() à une variable, puis à se demander pourquoi cette variable vaut None. Utilisez toujours sorted() lorsque vous avez besoin de la version triée tout en conservant l’original.

Le tri de Python accepte une fonction key évaluée une seule fois par élément (contrairement au comparateur de C, appelé pour chaque paire). Parmi les clés de tri courantes en entretien, on trouve len pour la longueur d’une chaîne, lambda x: -x pour un ordre décroissant, lambda x: (x[1], x[0]) pour un tri selon plusieurs clés, et str.lower pour ignorer la casse. Le tri de Python est garanti stable, ce qui permet aux tris selon plusieurs clés de fonctionner correctement.

Choisissez le tri adapté au contexte :

• Utilisez sorted()/list.sort() : choix par défaut pour tous les problèmes d’entretien — Timsort est optimal
• Tri par comptage : lorsque les valeurs sont de petits entiers bornés (de 0 à k, avec k petit)
• Tri par base : lorsque vous triez beaucoup d’entiers dont la largeur en bits ou le nombre de chiffres est connu
• Tri par compartiments : lorsque les données sont des nombres flottants uniformément répartis dans un intervalle connu
• Implémentez un tri fusion : lorsqu’on vous demande de coder à partir de zéro un tri stable en O(n log n)

De nombreux problèmes d’entretien demandent des résultats « semblables à un tri » sans exiger un tri complet. Pour trouver les k meilleurs éléments, un tas min de taille k s’exécute en O(n log k), ce qui est plus rapide que O(n log n) lorsque k << n. Pour trouver le k-ième plus grand élément, la sélection rapide s’exécute en O(n) en moyenne. Pour trouver la médiane, l’approche à deux tas s’exécute en O(log n) par insertion. Ces approches de tri partiel sont à connaître, car elles constituent des solutions plus rapides qu’un tri complet.

La stabilité permet d’effectuer correctement un tri selon plusieurs clés : triez d’abord selon la clé secondaire (de manière stable), puis selon la clé principale (également de manière stable). L’ordre secondaire est conservé pour les éléments ex æquo selon la clé principale. Cette technique est utilisée dans les bases de données (ORDER BY col1, col2) et dans le tri par base (chaque passage sur un chiffre doit être stable pour que l’algorithme global soit correct). Le tri de Python est toujours stable, ce qui rend ce modèle fiable.

Vérifiez votre compréhension des concepts de Structures de données et algorithmes — préparation aux entretiens de programmation abordés dans cette leçon.

Dans cette leçon, vous avez appris que : les tris par comparaison sont bornés inférieurement par O(n log n) — dépasser cette borne nécessite des informations ne reposant pas sur les comparaisons, comme des entiers bornés ; le tri par comptage atteint O(n + k) en comptant les fréquences, le tri par base traite les chiffres avec une complexité totale de O(d × (n + k)), et le tri par compartiments exploite une distribution uniforme pour atteindre O(n) en moyenne ; et le Timsort de Python est le choix pratique par défaut : stable, en O(n log n) dans le pire cas, en O(n) dans le meilleur cas et plus rapide que toute solution codée manuellement pour des données réelles. La prochaine étape consiste à maîtriser la recherche binaire classique.