j'ai entendu parlé du tri pigeonnier mais pas vu grand chose sur le web...
 
je cherche une adresse...

c'est pas la même chose que la trieuse ? tu as N éléments indexables   contenu dans un tableau de >=N emplacements -> tu mets chaque élément à sa place ?
 
http://www.nist.gov/dads/HTML/bucketsort.html

 
très possible

C'est pas très performant ce style de tri... Rapide, mais carrément gourmand en ressources...
 
En fait, ce tri n'est intéressant que si n < N (avec n = borne maximale et N nombre d'éléments)
 
A ce moment, en plus de trier, cet algo permet de "compresser" les données, puisque tu supprimes les doublons sans perdre l'information.
 
Enfin... C'est bien ce que je pense hein ?
 
Mettons le tableau :
 
a[0] = 5;
a[1] = 4;
a[2] = 1;
a[3] = 4;
a[4] = 2;
a[5] = 0;
a[6] = 3;
a[7] = 2;
a[8] = 5;
a[9] = 4;
a[10] = 0;
a[11] = 1;
a[12] = 2;
a[13] = 1;
a[14] = 4;
 
Ca donne :
 
b[0] = 2;
b[1] = 3;
b[2] = 3;
b[3] = 1;
b[4] = 4;
b[5] = 2;
 
=> On passe de 15 lignes à 6 lignes.
=> Les éléments sont ordonnés
 
Par contre, imaginons un tableau :
 
a[0] = 15;
a[1] = 0;
a[2] = 65465465465;
 
Et là on pleure

Cela s'appelle plus précisément le tri par comptage (Counting sort en anglais)...c'est l'algorithme LE PLUS performant en terme d'utilisation CPU.
Cependant de GROS inconvénients :
 
1) Si l'écart entre la valeur min et la valeur max de ton tableau initial est énorme, ton tableau de distribution sera lui aussi enorme => complexité mémoire TROP importante.
 
2) Aucune comparaison n'est faite entre les valeurs => impossible de rendre ce tri GENERIQUE s'appliquant à tout type de données (par exemple trier un tableau de structure)car aucune fonction de comparaison n'est utilisée.
 
Ce type de tri est donc réservé que dans dans cas bien précis connue de l'utilisateur :
 
Par exemple en imagerie, trié un tableau contenant les differents niveau de gris d'une image : on sait dc que les valeurs seront comprises entre 0 et 255 => le tableau de distribution sera petit et triera très vite le tableau en un temps linéaire.

 
Rien ne t'empeche de faire plusieurs passes,
pour trier un entier ou un flottant stocké sur 32 bits
quatre passes de tri et une passe de comptage avec quatre tableaux de 256 compteurs suffisent.
 

 
Il ne s'agit pas d'un tri de comparaison, les données à déplacer sont dans un ordre déjà connu, contrairement à des données quelconque a qui on aurait adjoint une fonction de comparaison sous forme de boite noire. Puisque les données sont déjà triées on peut les déplacer directement là où elles doivent se trouver.
 
LeGreg

 
Si tu peux ramener ton tri de structure à un comptage  
alors ça ne fait aucune différence.
Exemple: placer des mots dans un dictionnaire,
tu commences par regarder leur premieres lettre et si c'est P tu les mets directement dans la case P.
 
Le fait qu'il y ait un comptage est la uniquement pour rendre compte du fait qu'on cherche à avoir la structure la plus compacte (vecteur), bien évidemment s'il s'agit de mettre des objets dans des cases à contenance infinie (listes chainées), pas vraiment besoin de comptage.
 
LeGreg

non, ça ce n'est pas le tri par comptage. le tri par comptage, c'est pour chaque élément, tu comptes à combien d'éléments il est inférieure, tu l'insères, et tu recommences.