Tri par base
Découvreur ou inventeur | |
---|---|
Date de découverte | |
Problème lié | |
Structure des données |
Pire cas |
---|
Pire cas |
---|
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 l'ordre lexicographique. Cet algorithme a besoin d'être couplé avec un ou plusieurs algorithmes de tri stable.
Principe
Le principe de l'algorithme est le suivant :
- On considère le chiffre le moins significatif de chaque clef.
- On trie la liste des éléments selon ce chiffre avec un algorithme de tri stable. Il y a une conservation de l'ordre des éléments ayant le même chiffre car le tri est stable.
- On répète l'étape 2 en regardant le chiffre suivant.
Comme on le verra dans les exemples, un chiffre peut être une valeur d'une carte, une couleur d'une carte, un chiffre dans l'écriture décimale d'un nombre, un bit ou un groupe de bits.
Exemples
Tri d'une liste d'entier
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. L'algorithme fonctionne comme suit.
- 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 trie la liste obtenue en triant par ordre croissant du chiffre des dizaines en utilisant un tri stable. On obtient: 2, 802, 24, 45, 66, 170, 75, 90. Ici 170 est avant 75 car on a utilisé un tri stable qui par définition ne modifie pas l'ordre initial des nombres ayant une clé identique, ici le chiffre des dizaines 7.
- On trie cette nouvelle liste en triant par ordre croissant du chiffre des centaines en utilisant un tri stable. On obtient alors la liste triée 2, 24, 45, 66, 75, 90, 170, 802. Les nombres de 2 à 90 n'ont pas de chiffre des centaines, on ne change donc pas la position obtenue précédemment.
Tri d'un jeu de 52 cartes
On peut également utiliser cet algorithme pour trier un jeu de 52 cartes[1] dans l'ordre lexicographique
obtenu avec l'ordre sur les valeurs (nombre ou tête de la carte) et l'ordre sur les enseignes (ou couleurs).
L'algorithme fonctionne comme suit.
- On prend un paquet de cartes et on fait treize tas pour ranger les cartes en fonction de la valeur de la carte. On obtient donc une pile d'as, de deux et ainsi de suite. On fusionne ensuite ces piles de manière à obtenir un paquet avec 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. Cette opération est stable : les cartes de chaque pile sont triés selon la valeur. 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.
Pseudo-code
En toute généralité, pour un tableau T
d'éléments codés sur chiffres, l'algorithme de tri par base[2] est :
fonction triParBase(T, d): Pour i allant de 1 à d Trier avec un tri stable le tableau T selon le i-ème chiffre
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 chiffre un nombre fini de valeurs possibles ordonnées de 1 à pour tout , on utilise une variante du tri comptage. 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 T
rangés par leur ordre d'apparition dans T
(ce qui assure la stabilité du tri) tels que leur i-ème chiffre soit à .
Historique
![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.](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7e/SEACComputer_038.jpg/168px-SEACComputer_038.jpg)
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[1].
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[1]. 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ée par Seward était de faire une passe linéaire sur tous les éléments de la liste pour connaître le nombre et la taille 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
Pour un tableau de taille d'éléments codés sur chiffres 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[2].
De manière générale, si le -ème chiffre 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.[2] 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 [1].
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[2].
Article connexe
Lien externe
- Démonstration et comparaison du tri par base (en) avec du JavaScript
Notes et références
- (en) Knuth, Donald Ervin, The art of computer programming, Addison-Wesley Pub. Co, ©1973-©1981 (ISBN 0-201-03809-9, 9780201038095 et 0201896842, OCLC 823849, lire en ligne), Section 5.2.5: Sorting by Distribution, pages 168-179
- Cormen, Thomas H., et Kocher, Georges-Louis, (trad. de l'anglais), Algorithmique : cours avec 957 exercices et 158 problèmes, Paris, Dunod, impr. 2010, 1188 p. (ISBN 978-2-10-054526-1 et 2-10-054526-4, OCLC 690855992, lire en ligne), p. 8.3 Tri par base, 182-185
- (en) Aspray, William., Computing before computers, Ames, Iowa State University Press, , 266 p. (ISBN 0-8138-0047-1 et 9780813800479, OCLC 20690584, lire en ligne), Chapitre 4: Punched-Card Machinery, page 140
- (en) « I Wrote a Faster Sorting Algorithm », sur Probably Dance, (consulté le )
- (en) « Is radix sort faster than quicksort for integer arrays? », sur erik.gorset.no (consulté le )
- (en) « Function template integer_sort - 1.62.0 », sur www.boost.org (consulté le )