Motivation

Le tri par comptage (Counting Sort) ne compare jamais deux éléments. Il utilise leurs valeurs directement comme indices dans un tableau de comptage (count), ce qui lui permet de s'exécuter en temps linéaire.

Pourquoi apprendre le tri par comptage ?

• Temps linéaire : il s'exécute en O(n + k), où n est le nombre d'éléments et k est la plage de valeurs. Lorsque k est petit, cela surpasse le O(n log n).
• Stable (lorsqu'il est effectué avec soin) : une base pour le tri radix (Radix Sort), qui enchaîne plusieurs passes de tri par comptage.
• Une idée différente : trier en comptant les valeurs plutôt qu'en les comparant.

Le compromis : il nécessite O(k) de mémoire pour le tableau de comptage, il est donc peu adapté lorsque la plage de valeurs est immense (par exemple, trier une poignée de nombres allant jusqu'à un milliard).