Tri par comptage et tri par base : algorithmes et applications

1. Au-delà des comparaisons : les tris en temps linéaire

Pour introduire ce changement de paradigme, je vous invite à visionner un court extrait d'une conférence du MIT. Il expose les hypothèses fondamentales qui nous permettront de concevoir des algorithmes de tri plus rapides.

2. Le tri par comptage (Counting Sort)

Le tri par comptage est le premier exemple de cette nouvelle approche. Son idée est d'une simplicité redoutable : au lieu de comparer les éléments entre eux, nous allons simplement compter le nombre d'occurrences de chaque valeur.

Principe et Mécanisme

Le tri par comptage s'applique lorsque les $n$ éléments à trier sont des entiers dans un intervalle connu [0...k-1].
L'algorithme se déroule en plusieurs étapes précises. Pour les comprendre en détail, je vous propose de vous appuyer sur un excellent document en français.

Pour résumer et visualiser la version stable de l'algorithme (celle du document) :

1. Comptage : On crée un tableau C de taille k et on compte les occurrences de chaque clé de l'entrée A. C[i] contient le nombre d'éléments égaux à i.
2. Positions cumulées : On modifie C pour que C[i] contienne le nombre d'éléments inférieurs ou égaux à i. C[i] indique maintenant la position finale dans le tableau de sortie du dernier élément de valeur i.
3. Placement : On parcourt le tableau d'entrée A de la fin vers le début. Pour chaque élément A[j], on le place dans le tableau de sortie B à la position C[A[j]] - 1 (en indexation 0), puis on décrémente C[A[j]].

Stabilité

La stabilité est une propriété fondamentale pour un algorithme de tri. Elle garantit que l'ordre relatif des éléments de même clé est préservé.

Pourquoi le parcours inverse (étape 3) garantit-il la stabilité ? En traitant les éléments de A de droite à gauche, on place le dernier élément d'une certaine clé en premier, à la position la plus à droite qui lui est réservée. Ensuite, l'avant-dernier élément de cette même clé sera placé juste avant, et ainsi de suite. L'ordre initial est donc bien préservé.

La vidéo suivante offre une excellente animation de ce processus.

Analyse et Conditions d'Application

• Complexité temporelle : $\Theta (n+k)$. Les étapes (initialisation, comptage, cumul, placement) sont toutes en $\Theta (k)$ ou $\Theta (n)$.
• Complexité spatiale : $\Theta (n+k)$ (pour le tableau de sortie B et le tableau de comptage C).
• Condition d'application principale : L'algorithme est efficace si $k=O(n)$. Si l'étendue k devient beaucoup plus grande que n (par exemple, $k=n^2$), la complexité temps et espace devient prohibitive.

3. Le tri par base (Radix Sort)

Comment trier efficacement des entiers lorsque l'étendue k est grande ? Par exemple, si nous devons trier $1$ million de nombres ( $n=10^6$ ) de 32 bits ( $k\approx 4\cdot 10^9$ ). Le tri par comptage est ici impraticable.

Le tri par base résout ce problème en triant les nombres "chiffre par chiffre".

Principe et Mécanisme

L'idée est de décomposer les nombres dans une base $b$ (par exemple, base 10 pour nos chiffres décimaux, ou base 2 pour les bits) et d'appliquer un tri stable sur chaque "chiffre", en commençant par le moins significatif (LSD : Least Significant Digit).

1. Considérez les nombres à trier comme des chaînes de $d$ chiffres.
2. Pour $i$ allant de 1 à $d$ (du chiffre le moins significatif au plus significatif) :
   • Triez le tableau en utilisant un tri stable (comme notre tri par comptage) basé sur la valeur du $i$-ème chiffre.

La raison pour laquelle cette approche fonctionne repose entièrement sur la stabilité du tri intermédiaire. Après avoir trié par le $i$-ème chiffre, deux nombres ayant le même $i$-ème chiffre conservent leur ordre relatif, qui a été établi par les tris sur les chiffres $1,...,i-1$.

Analyse et Conditions d'Application

• Complexité temporelle : Soit $n$ nombres, $d$ chiffres par nombre, et une base $b$ (chaque chiffre peut prendre $b$ valeurs). Nous effectuons $d$ passes de tri par comptage. Chaque passe a une complexité de $\Theta (n+b)$. La complexité totale est donc $\Theta (d(n+b))$.
• Choisir la base $b$ : C'est un point clé. Pour des nombres allant jusqu'à une valeur $k$, on a $d\approx {\log }_{b}k$. La complexité est donc $\Theta (({\log }_{b}k)(n+b))$. Un choix judicieux, si la mémoire le permet, est de prendre $b\approx n$.
  • Si $b=n$, et que les clés sont bornées par $k\le n^c$ pour une constante $c$, alors $d={\log }_{n}k\le {\log }_n(n^c)=c$.
  • La complexité devient $\Theta (c(n+n))=\Theta (cn)=\Theta (n)$.
  • Le tri par base permet donc de trier en temps linéaire des entiers dont la valeur est polynomiale en $n$.

La vidéo suivante détaille cette analyse et le choix de la base.

4. Exercice d'implémentation

Votre aisance en Python est un atout. Je vous propose de mettre en pratique ces deux algorithmes.

1. counting_sort(A, k, key_extractor)

   • Implémentez la version stable du tri par comptage.
   • A est la liste d'objets à trier.
   • k est la valeur maximale de la clé + 1.
   • key_extractor est une fonction (par exemple, une lambda) qui, pour un élément de A, retourne la clé entière sur laquelle trier.

2. radix_sort(A, d, base)

   • Implémentez le tri par base pour une liste A d'entiers non-négatifs.
   • d est le nombre de chiffres, base est la base de numération.
   • À l'intérieur, vous appellerez votre counting_sort en boucle. Pour chaque passe $i$, le key_extractor devra extraire le $i$-ème chiffre d'un nombre.
   • Aide pour le key_extractor : le $i$-ème chiffre (avec $i=0$ pour le moins significatif) d'un nombre x en base b est (x // (base**i)) % base.

Essayez d'abord d'écrire ces fonctions vous-même. Les pseudo-codes dans les ressources sont des guides excellents.

Conclusion

Aujourd'hui, nous avons exploré une famille d'algorithmes radicalement différente. En renonçant au modèle de comparaison et en exploitant la structure des clés entières, nous avons atteint des performances en temps linéaire, chose impossible autrement.

Points clés à retenir :

• Tri par comptage : Principe simple et efficace ($\Theta (n+k)$), mais limité aux cas où l'étendue des clés k est de l'ordre de n.
• Tri par base : Généralise le tri par comptage à des étendues de clés bien plus grandes (polynomiales en n) en triant chiffre par chiffre. Sa complexité $\Theta (d(n+b))$ peut être rendue linéaire par un choix judicieux de la base b.
• Stabilité : Cette propriété n'est pas un simple détail technique. C'est la condition sine qua non du bon fonctionnement du tri par base LSD.

Prochaine étape :
Nous avons maintenant vu comment "battre" la borne $\Omega (n\log n)$. Dans la prochaine et dernière leçon de ce module, nous allons justement prouver formellement cette borne inférieure pour les tris par comparaison en utilisant le modèle de l'arbre de décision. Cela vous donnera une compréhension complète et rigoureuse du paysage des algorithmes de tri.