Tri par casier
Presentation
Le tri par casiers est une méthode de tri très spéciale car elle ne s’applique qu’au tri de valeurs entières incluses dans un ensemble par trop grand. Cette contrainte réduit énormément la portée des utilisations de ce tri, mais quand ce tri est implémentable, il est d’une redoutable efficacité. Cela est du au fait que c’est la seule méthode de tri qui ne nécessite aucune comparaison entre les différents éléments.
Son principe est le suivant :
Il faut rechercher dans l’ensemble d’éléments le plus petit élément u et le plus grand élément v.
Dans un deuxième temps, un tableau de taille (v-u+1) dont toutes les valeurs sont initialisés à 0 est construit.
Ensuite, l’ensemble des valeurs à classer est parcourut, et pour chaque valeur x, la case n° (x-u) est incrémentée.
Enfin, le tableau est parcourut et l’ensemble des éléments est recomposé en créant pour chaque case, autant de valeurs qu’indiques son contenu.
Exemple
Soit l’ensemble d’entiers à trier suivant :
| 4 | 0 | -1 | 2 | 0 | 0 | 2 | 5 | -1 | 2 | 0 | 4 | 2 |
Le plus petit élément u=(-1) et le plus grand élément v=(5), un tableau de taille v-u+1=7 est donc construit, il est initialisé à 0. Ensuite, on considére chaque élément x de l’ensemble à classer et on incrémente la case (x-u) du tableau. Soit les différentes étapes suivantes avec en rouge l’élément x considéré et en bleu la case qui est incrémentée :
| N° de case | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| Elément x correspondant | -1 | 0 | 1 | 2 | 3 | 4 | 5 | |
| Tableau initial | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| E l é m e n t x |
4 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | |
| -1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | |
| 2 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | |
| 0 | 1 | 2 | 0 | 1 | 0 | 1 | 0 | |
| 0 | 1 | 3 | 0 | 1 | 0 | 1 | 0 | |
| 2 | 1 | 3 | 0 | 2 | 0 | 1 | 0 | |
| 5 | 1 | 3 | 0 | 2 | 0 | 1 | 1 | |
| -1 | 2 | 3 | 0 | 2 | 0 | 1 | 1 | |
| 2 | 2 | 3 | 0 | 3 | 0 | 1 | 1 | |
| 0 | 2 | 4 | 0 | 3 | 0 | 1 | 1 | |
| 4 | 2 | 4 | 0 | 3 | 0 | 2 | 1 | |
| 2 | 2 | 4 | 0 | 4 | 0 | 2 | 1 | |
Ensuite, on va reconstituer l’ensemble des valeurs classées :
| D'aprés le tableau on a | Soit l'ensemble suivant : | ||||||||||||
| 2 fois -1 | -1 | -1 | |||||||||||
| 4 fois 0 | -1 | -1 | 0 | 0 | 0 | 0 | |||||||
| 0 fois 1 | -1 | -1 | 0 | 0 | 0 | 0 | |||||||
| 4 fois 2 | -1 | -1 | 0 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | |||
| 0 fois 3 | -1 | -1 | 0 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | |||
| 2 fois 4 | -1 | -1 | 0 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 4 | 4 | |
| 1 fois 5 | -1 | -1 | 0 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 4 | 4 | 5 |
On a ainsi récupéré l’ensemble des valeurs classées ! C’est ce que l’on souhaitait obtenir...
| Pseudo langage | |||||||
| C / C++ | Caml | Java | OCaml | ||||
| Caml (listes) | OCaml (listes) | ||||||
Complexité
Le calcul de la complexité pour ce tri est relativement simple. Considérons un ensemble de n éléments. Dans un premier temps, il faut parcourir une fois la liste pour trouver le plus petit élément u et le plus grand élément v. Soit une complexité en O(n).
Ensuite, il faut construire un tableau à m=v-u+1 éléments et initialiser ce tableau à 0. Soit une complexité en O(m). L’espace mémoire alloué pour créer un tel tableau est également proportionnel à m.
Ensuite, on parcours l’ensemble des éléments en incrémentant la case correspondante du tableau, soit une complexité pour le parcours en O(n).
Enfin, on parcours les différentes cases du tableau et on reconstruit l’ensemble des éléments en le classant, soit une complexité pour le parcours en O(m).
Au final, on a une complexité en nombre d’opérations qui est en O(m+n). On remarque donc que la complexité est linéaire, elle dépend également de l’intervalle de valeur m que prend les entiers à classer. Le tri sera d’autant plus efficace que l’intervalle de valeurs sera réduit. En effet, prenons le cas extrême d’une dizaine de valeurs entières à classer comprises entre -1000 et 1000. Le tri est très simple, mais l’application du tri casier sur ce type de tri entraînera la création d’un tableau de 2000 valeurs, ce qui bien trop important pour ne classer que 10 valeurs.
Le tri sera d’autant plus efficace que l’intervalle sera réduit et que le nombre de valeurs à classer sera élevé. En gros, plus le rapport n/m est grand, plus le tri est avantageux. En effet, si n est très grand, aucun tri ne pourra rivaliser en vitesse de classement avec le tri casier, si m est très petit, l’efficacité sera encore plus grande puisque l’espace mémoire nécessaire sera moins important. L’idéal serait également qu’il n’y ait pas trop de trous dans l’ensemble, c’est à dire que la plupart des valeurs de l’intervalle se retrouvent dans l’ensemble à trier. En effet, même si une valeur n’apparaît pas, elle requiert une case dans le tableau intermédiaire, ce qui correspond à de l’allocation mémoire inutile.
Ce tri est donc très efficace, mais il est limité par les spécificités de chaque langage, on ne peut classer des valeurs comprises dans un intervalle plus grand que la taille maximale d’un tableau (qui est propre à chaque langage) et un élément ne doit pas se retrouver plus de fois que la taille du plus grand entier (qui est également propre à chaque langage).
En conclusion, le tri par casiers est l’un des tris les plus efficaces, mais son usage est malheureusement soumis à certaines régles qui limite fortement son champ d’utilisation.
Accueil des algorithmes de tri
Article précédent : le tri par Arbre Binaire de Recherche
Article suivant : comparaison de performances
