Tri par base

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En algorithmique le tri par base, ou tri radix de radix sort en anglais, est un algorithme de tri, utilisé pour ordonner des éléments identifiés par une clef unique. Chaque clef est une chaîne de caractères ou un nombre que le tri par base trie selon un ordre lexicographique. Cet algorithme a besoin d'être couplé avec un ou plusieurs algorithmes de tri stable.

Principe[modifier | modifier le code]

Le principe de l'algorithme est le suivant :

  1. On prend le chiffre (ou le groupe de bits) le moins significatif de chaque clef.
  2. On trie la liste des éléments selon ce chiffre (ou ce groupe de bits) avec l'algorithme de tri stable correspondant. Il y a une conservation de l'ordre des éléments ayant le même chiffre car le tri est stable.
  3. On répète l'étape 2 en regardant le chiffre (ou groupe de bit) suivant.

Algorithme[modifier | modifier le code]

En toute généralité, pour un tableau L d'éléments codés sur groupes de bits, l'algorithme de tri par base[1] est :

fonction triParBase(L, d):
   Pour i allant de 1 à d
       Trier les éléments de L selon leur i-ème groupe de bits

Le travail de l'algorithme réside donc dans les algorithmes de tri stable utilisés. Généralement, étant donné que le i-ème groupe de bits prend un nombre fini de valeurs possibles ordonnées de 1 à pour tout , une variante du tri comptage est utilisée. Après obtention de l'histogramme his des données du tri comptage, on crée un tableau tab de taille où, si , tab[k] contient un tableau de taille his[k] des éléments de L rangés par leur ordre d'apparition dans L (ce qui assure la stabilité du tri) tels que leur i-ème groupe de bit soit celui correspondant à .

Exemple[modifier | modifier le code]

Tri d'une liste d'entier.[modifier | modifier le code]

Nous allons utiliser cet algorithme pour trier par ordre croissant la liste : 170, 45, 75, 90, 2, 24, 802, 66.

Ici, le chiffre le moins significatif est le chiffre des unités, ensuite celui des dizaines et enfin celui des centaines.


On commence par trier la liste par ordre croissant du chiffre des unités. On obtient: 170, 90, 2, 802, 24, 45, 75, 66. On remarque que l'on a 170 avant 90 dans la nouvelle liste car dans la liste précédente, 170 était avant 90. Cela est du à l'utilisation d'un tri stable pour effectuer ce premier tri.

On trie la liste obtenue en triant par ordre croissant du chiffre des dizaines. On obtient: 2, 802, 24, 45, 66, 170, 75, 90.

On trie cette nouvelle liste en triant par ordre croissant du chiffre des centaines. On obtient: 2, 24, 45, 66, 75, 90, 170, 802.

Tri d'un jeu de 52 cartes.[modifier | modifier le code]

Exécution de l'algorithme de tri par base sur un paquet de 52 cartes. (Cliquer pour lancer l'animation)

On peut également utiliser cet algorithme pour trier un jeu de 52 cartes[2] en

utilisant les ordres suivants:

et et en utilisant l'ordre lexicographique:

Pour faire cela, on prend un paquet de cartes et on fait treize tas pour ranger les cartes en fonction du nombre ou de la tête sur la carte. On a donc une pile d'as, de deux et ainsi de suite. On fusionne ensuite ces piles de manière à pouvoir prendre les as en premier, puis les deux et ainsi de suite jusqu'aux rois. Maintenant, on fait quatre tas pour ranger les cartes en fonctions de leurs couleurs. On pose les cartes sous chaque pile en les posant une à une. On fusionne ensuite les paquets de manière à avoir d'abord les carreaux, puis les trèfles, puis les cœurs et enfin les piques. Le paquet ainsi obtenu est trié dans l'ordre lexicographique.

Historique[modifier | modifier le code]

Une trieuse IBM : en haut à gauche de la machine se trouve un tas de cartes perforées. Une sorte de tapis roulant permet de tester l'emplacement des perforations sur la carte et range la carte dans le panier associé se situant en bas de la machine. Il y a en tout treize paniers.
Une trieuse IBM de cartes perforées effectuant un tri par base. On y remarque les treize cases où la machine range les cartes perforées.

Dans le début du XXe siècle, Herman Hollerith et E.A.Ford ont amélioré l'efficacité des tabulatrices en créant une trieuse automatique de cartes perforées qui repose sur le principe du tri par base[3]. L'opérateur sélectionnait une colonne, puis mettait les cartes perforées dans la trieuse. La trieuse rangeait les cartes dans l'une des treize cases. Les douze premières cases correspondaient aux cartes ayant l'une des douze positions de perforations possibles sur la colonne choisie par l'opérateur, et la treizième case correspondait aux cartes sans perforation sur la colonne. En répétant l'opération autant de fois que de colonnes et en conservant l'ordre de chaque cases, c'est-à-dire en mettant dans la trieuse les cartes de la premiers case puis celles de la deuxième et ainsi de suite, les cartes perforées étaient triées. En 1923, le tri par base était communément utilisé pour trier les cartes perforées[2].

En 1954 Harold H. Seward (en) a développé, dans sa thèse de master au MIT, le premier algorithme de tri par base implémenté sur ordinateur[2]. Les algorithmes précédents ne fonctionnaient pas sur ordinateur car ils avaient besoin d'une quantité imprévisible d'espace mémoire en créant un nombre indéterminé de listes de tailles inconnus pour faire les différents tris. L'innovation proposé par Seward était de faire une passe linéaire sur tous les éléments de la liste pour connaitre le nombre et la tailles des tableaux auxiliaires à créer et d'ensuite appliquer l'algorithme de tri par base en rangeant les éléments dans ces tableaux auxiliaires qui correspondent aux treize cases de sorties des trieuses de Hollerith.

Désormais, le tri par base est appliqué pour trier les chaines de caractères binaire et les entiers. Ce tri est en moyenne plus rapide que les autres algorithmes et est parfois 50% plus rapide ou trois fois plus rapide[4],[5],[6].


Complexité et caractéristiques[modifier | modifier le code]

Pour un tableau de taille d'éléments codés sur groupes de bits pouvant prendre valeurs possibles, le temps d'exécution est en si le tri stable employé s'effectue en , ce qui est le cas du tri comptage[1].

De manière générale, si le -ème groupe de bits peut prendre valeurs possibles, la complexité temporelle est en . Par exemple, dans le cas du tri d'un jeu de 52 cartes, on a et .

Lorsque est constant et que , la complexité en temps du tri par base est linéaire.[1] Ceci est souvent le cas dans le paradigme de la programmation par contrat, où les valeurs de et sont fixées à l'avance. Par exemple, c'est le cas lorsqu'on trie par ordre lexicographique des mots de la langue française où est majoré par 30 et vaut 42 (nombre de lettres totales dans l'alphabet français en comptant les lettres accentuées). Cela rend ce tri plus rapide que les tris par comparaison (comme les tris rapide, par tas et fusion), qui sont en [2].

Le plus grand désavantage du tri par base est qu'il nécessite espace mémoire supplémentaire et il requiert une analyse de chaque caractère des clefs de la liste d'entrée, il peut donc être très lent pour des clefs longues. Si l'espace mémoire est limité, on préférera employer un tri en place, ce qui diminuera la complexité spatiale mais augmentera la complexité temporelle[1].

Notes et références[modifier | modifier le code]

  1. a b c et d Cormen, Thomas H., et Kocher, Georges-Louis,, Algorithmique cours avec 957 exercices et 158 problèmes, Dunod, impr. 2010 (ISBN 978-2-10-054526-1 et 2-10-054526-4, OCLC 690855992, lire en ligne), p. 8.3 Tri par base, 182-185
  2. a b c et d (en) Knuth, Donald Ervin, The art of computer programming, Addison-Wesley Pub. Co, ©1973-©1981 (ISBN 0201038099, 9780201038095 et 0201896842, OCLC 823849, lire en ligne), Section 5.2.5: Sorting by Distribution, pages 168-179
  3. (en) Aspray, William., Computing before computers, Iowa State University Press, (ISBN 0813800471 et 9780813800479, OCLC 20690584, lire en ligne), p. Chapitre 4: Punched-Card Machinery, page 140
  4. (en) « I Wrote a Faster Sorting Algorithm », sur Probably Dance, (consulté le 16 novembre 2019)
  5. (en) « Is radix sort faster than quicksort for integer arrays? », sur erik.gorset.no (consulté le 16 novembre 2019)
  6. (en) « Function template integer_sort - 1.62.0 », sur www.boost.org (consulté le 16 novembre 2019)

Lien externe[modifier | modifier le code]