Tri par base
Le tri par base est à part parmi les algorithmes de tri : il ne demande jamais laquelle de deux valeurs est la plus grande. Il lit les nombres chiffre par chiffre et les trie selon un chiffre à la fois, avec dix casiers. L'idée est plus ancienne que les ordinateurs : c'est ainsi que fonctionnaient les trieuses de cartes perforées.
L'idée
Triez les nombres selon leur seul chiffre des unités. Puis triez-les selon leur chiffre des dizaines, mais en gardant les nombres qui ont le même chiffre des dizaines dans l'ordre donné par le premier passage. Puis selon les centaines, de la même façon. Après le dernier passage, la liste est triée : les centaines décident d'abord, à centaines égales les nombres sont déjà dans l'ordre de leurs dizaines, et à dizaines égales dans l'ordre de leurs unités.
Un passage, avec des casiers
Chaque passage utilise dix casiers, un pour chaque chiffre de 0 à 9. Parcourez la liste du début à la fin et placez chaque nombre dans le casier de son chiffre, derrière les nombres qui y sont déjà. Puis videz les casiers dans la liste dans l'ordre, le casier 0 en premier. C'est le fait de déplacer les nombres dans l'ordre de la liste et de les ajouter au fond d'un casier qui rend le passage stable. L'application compte d'abord les nombres pour chaque chiffre, pour que les casiers tiennent côte à côte sur une seule ligne, chacun commençant juste après le précédent : c'est un tri par comptage sur un chiffre.
Un exemple
Prenez 170, 45, 75, 90, 802, 24, 2, 66. Selon le chiffre des unités : 170, 90, 802, 2, 24, 45, 75, 66. Selon le chiffre des dizaines : 802, 2, 24, 45, 66, 170, 75, 90 ; notez que 802 et 2, qui ont tous deux 0 comme chiffre des dizaines, gardent leur ordre du premier passage. Selon le chiffre des centaines : 2, 24, 45, 66, 75, 90, 170, 802. Trois passages sur huit nombres : 24 chiffres lus et 48 déplacements, et pas une seule comparaison.
Quelle est sa vitesse ?
Chaque passage lit un chiffre de chaque nombre et déplace chaque nombre deux fois : pour n nombres à d chiffres, le travail croît donc avec n · d. Un tri par comparaison fait au moins environ n log₂ n comparaisons dans le pire cas, car il doit distinguer n! ordres possibles une question oui-ou-non à la fois. Le tri par base n'est pas soumis à cette limite, puisqu'il ne pose jamais de telles questions. Pour beaucoup de clés courtes, comme un million de nombres inférieurs à 1 000, trois passages représentent bien moins de travail que les quelque 20 millions de comparaisons d'un tri par comparaison. Pour des clés longues ou peu de valeurs, l'avantage disparaît.
LSD et MSD, et un peu d'histoire
La version montrée ici commence par le chiffre le moins significatif (LSD). Dans l'autre sens, en commençant par le chiffre le plus significatif (MSD), on répartit la liste en casiers selon le premier chiffre et on trie chaque casier séparément, ce qui convient aux chaînes de longueurs différentes. Le tri par base remonte aux trieuses de cartes perforées venues après les machines à tabuler d'Herman Hollerith, utilisées pour le recensement américain de 1890 : une trieuse faisait tomber chaque carte dans l'une de dix cases selon le trou d'une colonne, et les opérateurs passaient le paquet une fois par colonne, en commençant par la dernière.
À vous d'essayer
Ouvrez l'application et appuyez sur Étape. Chaque passage compte d'abord les chiffres, ce qui délimite les casiers 0 à 9 sur la ligne sous la liste. Puis les nombres tombent un par un dans leurs casiers, le casier actif en surbrillance, et sont recopiés. Saisissez vos propres nombres jusqu'à 999, comme l'exemple ci-dessus, pour voir les trois passages.
Questions fréquemment posées
Quelle est la complexité en temps du tri par base ?
O(n · d) pour n clés de d chiffres dans une base fixe, plus le coût des casiers à chaque passage. Il lui faut O(n) de mémoire en plus pour le tampon qui contient les casiers.
Le tri par base est-il stable ?
Le tri par base LSD doit l'être : il ne marche que parce que chaque passage garde les valeurs qui ont le même chiffre dans leur ordre d'arrivée. Le résultat final est donc stable lui aussi.
Le tri par base gère-t-il les nombres négatifs ou décimaux ?
Pas directement, mais c'est possible avec une astuce : décaler les nombres négatifs pour qu'ils soient tous positifs, ou les trier à part et inverser leur ordre. Les nombres à virgule flottante peuvent être triés selon leurs motifs de bits après une petite transformation.
Pourquoi la base 10 ?
Parce qu'elle est facile à suivre. Les ordinateurs trient en général par 8 ou 16 bits à la fois : un nombre de 32 bits demande donc quatre ou deux passages, avec 256 ou 65 536 casiers.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer le tri par base