- Casier actif
- Juste déplacée
- Recopiées
- En place
Tri par base
Le tri par base trie des nombres entiers sans jamais en comparer deux. Il trie la liste selon le chiffre des unités, puis des dizaines, puis des centaines, en plaçant chaque fois les valeurs dans dix casiers et en les recopiant dans l'ordre. Regardez les casiers se remplir sur la ligne sous la liste, un déplacement à la fois, et la liste se trier selon de plus en plus de chiffres. Appuyez sur Lecture pour regarder le tri, ou sur Étape et Retour pour avancer d'un déplacement à la fois. Faites glisser le curseur d'étapes pour aller n'importe où. Les casiers 0 à 9 sont côte à côte sur la ligne sous la liste. Les tuiles comptent les chiffres lus, les déplacements et les passages. Choisissez le nombre de barres, leur ordre de départ, ou saisissez vos propres nombres jusqu'à 999. Quand le tableau est sélectionné, les flèches avancent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Choisissez le nombre de barres et leur ordre de départ, ou saisissez vos propres nombres entiers jusqu'à 999 pour voir le passage des centaines.
- Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer d'une valeur à la fois. Faites glisser le curseur d'étapes pour aller n'importe où dans le tri.
- Suivez chaque passage : on compte les chiffres, on place chaque valeur dans son casier, puis on recopie les casiers.
Comment fonctionne le tri par base
Ne regardez que le dernier chiffre de chaque nombre et triez la liste selon ce chiffre : placez chaque nombre dans l'un des dix casiers, de 0 à 9, dans l'ordre où ils arrivent, puis recopiez les casiers l'un après l'autre. Faites de même avec le chiffre des dizaines, puis des centaines. Comme chaque passage garde l'ordre des nombres qui partagent un chiffre, les passages précédents décident toujours de leur ordre, et après le dernier passage, toute la liste est triée.
Aucune comparaison
Les tris par comparaison font au moins environ n log₂ n comparaisons dans le pire cas, quelle que soit l'astuce employée. Le tri par base contourne cette limite en lisant des chiffres à la place : chaque passage lit un chiffre de chaque valeur et déplace chaque valeur deux fois, donc d chiffres demandent d passages et le travail croît avec n · d. Pour de longues listes de clés courtes, c'est payant : un million de nombres jusqu'à 999 demandent trois passages, là où un tri par comparaison fait environ 20 millions de comparaisons. En contrepartie, il ne marche que pour des clés faites de chiffres ou de caractères, et il lui faut de la place pour les casiers.
Questions fréquemment posées
Comment fonctionne le tri par base ?
Il trie les nombres selon leur dernier chiffre, puis selon le chiffre précédent, et ainsi de suite jusqu'au premier chiffre. Chaque passage répartit les nombres dans dix casiers selon ce chiffre, en gardant leur ordre, puis recopie les casiers. Après le passage sur le chiffre le plus significatif, la liste est triée.
Pourquoi commencer par le dernier chiffre ?
Parce que chaque passage est stable : les nombres qui ont le même chiffre gardent l'ordre que leur ont donné les passages précédents. Le dernier passage, sur le premier chiffre, décide donc de l'ordre, et les égalités sont départagées par les chiffres déjà triés. C'est ce qu'on appelle le tri par base LSD (least significant digit, chiffre le moins significatif).
Le tri par base est-il plus rapide que le tri rapide ?
Il peut l'être, pour beaucoup de clés courtes : son travail croît avec le nombre de valeurs fois le nombre de chiffres, sans n log n. Pour peu de valeurs, des clés très longues ou des données qui ne sont pas faites de chiffres, le tri rapide et le tri fusion sont en général plus rapides et plus simples.
Quel lien avec le tri par comptage ?
Chaque passage du tri par base est un tri par comptage sur un chiffre : on compte combien de valeurs ont chaque chiffre, on calcule où commence chaque casier, et on y place les valeurs dans l'ordre.
Mes nombres sont-ils envoyés quelque part ?
Non. Le tri se fait dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur