Tri par base

Publié : 05/03/2016 · Modifié : 05/03/2016


Table des matières

Introduction

Le tri par base (radix sort en anglais) est un algorithme de tri ayant une complexité en temps linéaire, qui fut inventé à l'époque des trieuses de cartes perforées, mais il est encore utilisé de nos jours dans les ordinateurs modernes. Cet algorithme nécessite un autre algorithme de tri pour fonctionner, et ce dernier doit obligatoirement être stable.

Principe de l’algorithme

L’algorithme est simple, on va trier successivement (à l’aide d’un algorithme de tri stable) tous les chiffres des nombres donnés en entrée en commençant par le chiffre le moins significatif jusqu'au plus significatif.

C’est-à-dire que pour des nombres entiers, on va trier tout d’abord les nombres en fonction du chiffre de l’unité, puis trier de nouveau en fonction du chiffre des dizaines, et ainsi de suite jusqu’à atteindre le nombre maximum de chiffre contenu dans un nombre.

Il est important de noter que l’ordre de tri est défini dans l’algorithme de tri utilisé et non dans le tri par base en lui-même.

Exemple

Soit le tableau suivant que l’on souhaite trier dans l’ordre croissant en utilisant l’algorithme du tri par base : 56, 87, 2, 36, 74, 19.

Tout d’abord, on remarque qu’il y a au maximum deux chiffres par nombre et que par conséquent on utilisera notre algorithme de tri stable seulement deux fois. On commence donc par trier cette suite de nombre en fonction du chiffre des unités, puis on recommence l'opération sur le chiffre des dizaines :

Début 1er tour 2ème tour
56 2 2
87 74 19
2 56 36
36 36 56
74 87 74
19 19 87

On atteint le nombre maximum de chiffre, notre tableau est donc trié :

2, 19, 36, 56, 74, 87.

Exemple de tri par base
Exemple de tri par base

J'ai découpé les chiffres des nombres pour bien voir le tri de chacun, en bleu on retrouve nos étapes intermédiaires consistantes à trier en fonction d'un chiffre en particulier, et en vert notre tableau final trié.

Pseudo-code

Le pseudo-code du tri par base :

triBase :

   Pour chaque chiffre possible
      Trier Tableau en fonction du chiffre i

Cela peut paraitre assez étrange d'utiliser un autre algorithme de tri dans un algorithme de tri, mais si on se sert du tri par dénombrement on peut ainsi contrer plusieurs de ses défauts tout en gardant sa rapidité d'exécution. Tout d'abord, l'espace mémoire utilisé est bien plus optimisé car on évite les "trous" dans le tableau des effectifs, et ensuite on peut désormais trier des nombres décimaux puisque chaque chiffre reste un nombre entier qu'on peut employer avec le tri par dénombrement.

Complexité

La complexité de ce tri dépend forcément de l'algorithme de tri utilisé dans notre boucle principale, mais supposons qu'on utilise, comme précédemment évoqué, le tri par dénombrement. Pour rappel, ce tri a une complexité en $O(N + M)$ avec $N$ la taille du tableau, et $M$ l'élément maximum du tableau à trier. Soit $C$ le nombre de chiffres maximum d'un nombre du tableau, on a donc une complexité en temps pour notre algorithme de tri par base en $O(C(N + M))$, cependant comme notre tri par dénombrement sera uniquement utilisé sur des chiffres, ces derniers ne dépasseront jamais 9 (si on utilise une notation décimale bien sûr), et $M$ devient alors une constante insignifiante dans le calcul de la complexité, que l'on peut alors simplifier en $O(CN)$.

Implémentation

Pour implémenter le tri par base, il va tout d'abord falloir modifier légèrement notre implémentation du tri par dénombrement car la notion de stabilité pour ce tri n'a pas vraiment de sens puisqu'on utilise des effectifs sans lien réel avec notre tableau.

Voici une implémentation en C++ du tri par base :

tri_base.cpp

L'entrée de notre exemple :

6
56 87 2 36 74 19

En sortie le tableau trié :

2 19 36 56 74 87

Conclusion

Le tri par base est donc un algorithme de tri très rapide qui s'exécute en temps linéaire en se basant sur un autre algorithme de tri stable pour fonctionner. Il permet notamment de combler les avantages du tri par dénombrement, cependant ce n'est pas pour cela que ce dernier est bien plus efficace que d'autres algorithmes de tri en $O(N \log _2 N)$ comme le tri rapide et ceci pour plusieurs raisons :

Encore une fois, le choix d'un algorithme de tri par rapport à un autre dépend de multiples facteurs qu'il faut prendre en compte, d'autant plus que l'entrée peut aussi jouer un grand rôle dans ce choix. Le tri par base reste tout de même utile grâce à sa complexité en temps linéaire efficace.