Nicolas DAILLY
www.dailly.info > Dossiers techniques > Algorithmes de Tri > Tri par casier

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 :

40-120025-12042

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 case0123456
Elément x correspondant-1012345
Tableau initial0000000
E
l
é
m
e
n
t

x
40000010
00100010
-11100010
21101010
01201010
01301010
21302010
51302011
-12302011
22303011
02403011
42403021
22404021

Ensuite, on va reconstituer l’ensemble des valeurs classées :

D'aprés le tableau on aSoit l'ensemble suivant :
2 fois -1-1-1
4 fois 0-1-10000
0 fois 1-1-10000
4 fois 2-1-100002222
0 fois 3-1-100002222
2 fois 4-1-10000222244
1 fois 5-1-100002222445

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


© 2000-2017 ~ Nicolas Dailly
Page générée le 24/05/2017 à 23:35:01 ~ Site réalisé avec SPIP