Le tri à paniers

Le principe est assez simple. On va partir d'un exemple. Imaginons que j'aie cette liste à trier dans l'ordre croissant :

Code : Console

Bon. Dans le tri à paniers, la première étape, c'est de déterminer le nombre le plus petit de la liste, ainsi que le nombre le plus grand. Donc ici, ces nombres sont 2 et 12. Jusque là, c'est facile à comprendre et à implémenter .

Ensuite, nous allons créer 11 « paniers » : (12 - 2) + 1 = 11. Un panier est en réalité un compteur, que l'on initialise à 0. Il y en a (12 - 2) + 1 car c'est le nombre d'entiers compris entre 2 et 12. On crée donc un panier par nombre possible dans la liste (compris entre le minimum et le maximum). Chaque panier correspondra ainsi au nombre d'occurences dans la liste : le premier panier (numéro 2) contiendra le nombre de 2 dans la liste, le second (numéro 3) le nombre de 3 dans la liste, et ainsi de suite.

La formule pour avoir le nombre d'entiers entre min et max est (min-max)+1. Elle ne marche pas avec les réels, car entre deux réels il y a une infinité d'autres réels. Voilà pourquoi trier par paniers des réels est interdit : il y aurait une infinité de paniers !

Pour le moment on a donc :

Code : Console

L'étape suivante, ça va être de parcourir la liste à trier, du début à la fin, et, pour chaque valeur rencontrée, de rajouter 1 « jeton » dans le panier qui lui correspond (c'est à dire incrémenter le compteur).

Code : Console



C'est tout bête. On va réécrire entièrement la liste à trier à l'aide des paniers. En gros, on prend le 1^er panier, et on écrit sa valeur correspondante autant de fois qu'il y a de jetons dedans. On recommence avec le 2^ème panier, le 3^ème...

Exemple : dans le 1^er panier, le 02, il y a 1 jeton : on écrit une fois 02 dans le tableau. Le panier suivant, 03, ne contient rien. On passe. Le 04 contient 2 jetons : on écrit deux fois le nombre 04 dans le tableau. Et ainsi de suite...

On obtient alors :

Code : Console

Hourra ! La liste est triée \o/ !

Mon implémentation en C de cet algorithme n'étant pas encore prête, je vais me contenter de vous donner les grandes idées.

La première chose à faire, c'est de créer deux entiers qui seront les minima et maxima du tableau à trier. Ensuite, avec une boucle, vous déterminez leur valeur (utilisez une seule boucle pour les deux, c'est plus rapide ).

Code : C

Ensuite, créez un tableau de (max-min)+1 entiers de long. Ce tableau sera le groupe de paniers (chaque case étant un panier). Il faut l'initialiser a 0, donc on utilise calloc :

Code : C

Maintenant, il faut parcourir la liste pour incrémenter les paniers :

Code : C

Ici, liste[i] est la valeur rencontrée, et on fait - min pour obtenir l'index, dans le tableau paniers, du panier correspondant à cette valeur.

Enfin, on parcourt les paniers tout en récrivant le tableau :

Code : C

Et maintenant liste est triée .

Nous allons donc maintenant parler de la complexité de cet algorithme. Pour ceux qui ne connaissent pas, il s'agit de savoir combien d'opérations on doit faire pour trier un tableau de N chiffres, en utilisant notre méthode. La complexité peut nous servir à évaluer la vitesse d'un algorithme sur telle machine, ou encore à comparer les algorithmes entre eux.

Le problème, c'est qu'évaluer très précisément le nombre d'opérations est souvent long et/ou difficile (ça va ensemble ). On va donc se contenter de calculer un ordre de grandeur : la complexité. Pour faire cet ordre de grandeur, on va négliger les instructions, qui, sur les machines récentes, sont extrêmement rapides à exécuter (moins d'une milli-seconde). On va surtout s'intéresser aux boucles : ce sont elles qui prennent un temps non-négligeable. Et, pour faire simple, on va définir qu'un tour de boucle vaut 1. C'est la référence. Comme les boucles contiennent des instructions classiques qui sont super-rapides, il n'y a pas beaucoup de différences de l'une à l'autre (au niveau du temps), sauf s'il y a une boucle dans une boucle. Mais dans ce cas c'est une autre histoire .

Revenons donc au tri à paniers. Imaginons que nous lui donnions un tableau de 20 chiffres. Que va-t-il faire ?

• Il va déterminer le minimum et le maximum possibles dans le tableau. Il va donc parcourir une fois tout le tableau : il va faire 20 premières itérations.
• Il va allouer et initialiser un tableau de (max-min)+1 éléments. On a donc une boucle de (max-min)+1 tours qui se fait.
• Il va ensuite parcourir le tableau pour "remplir les paniers". Il parcourt alors le tableau du début à la fin : encore 20 itérations.
• Enfin, il va parcourir tous les paniers pour "remplir" le tableau. Comme il y a autant d'éléments au début et à la fin du tri, il y a donc, pour cette étape, autant d'itérations que de cases dans le tableau : 20.

Ainsi, on a 3*20 + (max-min)+1 tours de boucle. Bien. Ca nous fait 60+tailleIntervalle tours de boucle. Et comme on pourrait remplacer 20 par n'importe quel autre chiffre, on dit que pour un tableau de N chiffres, il faut donc 3*N + (max-min)+1 tours de boucle. C'est une première estimation.

Bon, cependant, il y a une chose que l'on a pas vue en complexité : les informaticiens et les logiciens estiment que, sur une machine moderne très rapide, le fait que l'algorithme mette une fois N, deux fois N où trois fois N (etc etc ...) tours pour s'exécuter n'est pas très important. Ce qui est important, c'est N. Quand N devient très très grand (plusieurs millions), le trois devient ridicule à côté et ne change plus grand chose.

Donc, quand on a 3*N tours de boucles, on "arrondit" tout ça à N, tout court. Ce qui nous done N + (max-min). On néglige aussi le +1, mais pas max-min car cette valeur peut devenir très très grande dans certains cas (si la liste est très disparate), contrairement à 3 qui restera toujours tout petit.

On note donc que cet algorithme a une complexité O(N + (max-min)). Ce qui fait que la complexité augmente avec le nombre d'éléments et la disparité de la liste. Par rapport aux autres algorithmes, c'est pas super, surtout quand la liste est très disparate. Mais face à une liste d'éléments très proches (les âges d'une classe [...]) ça peut servir, la différence devenant plus petite. Cet algorithme peut même se révéler bien plus rapide que les tris « classiques ».