Tri par base
Un article de Wikipédia, l'encyclopédie libre.
Le tri par base (ou tri radix) est, en informatique, un algorithme de tri rapide et stable qui peut être 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 lexical.
Le temps d'exécution est O(nk) où n est le nombre d'objets et k la taille moyenne des clefs. Cet algorithme était utilisé pour trier des cartes perforées en plusieurs passages.
Le tri par base a été réutilisé comme une alternative à des algorithmes de tri plus puissants (comme les tris rapides, par tas et par fusion) qui demandent O(n log n) comparaisons où n est le nombre d'objets à trier. Ces algorithmes sont plus efficaces pour trier des données selon un ordre qui n'est pas lexical, mais c'est de peu d'importance pour les applications pratiques.
Si la taille de l'espace possible de clefs est proportionnel au nombre d'éléments, alors chaque clef aura une taille de log n caractères et le tri par base s'effectura en un temps O(n log n) dans ce cas.
En pratique, si les clefs utilisées sont de petits entiers, le tri peut être réalisé en deux temps, les comparaisons peuvent alors être faite avec quelques opérations qui opèrent en un temps constant. Dans ce cas, le tri par base s'exécutera en O(n) et en pratique il s'avérera plus rapide que d'autres algorithmes de tri.
Le plus grand désavantage du tri par base est qu'il nécessite O(n) 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.
L'ordre de tri est typiquement le suivant : les clefs courtes viennent avant les clefs longues, les clefs de même taille sont triées selon un ordre lexical. Cette méthode correspond à l'ordre naturel des nombres s'ils sont représentés par des chaînes de chiffres.
Son mode opératoire est :
- prend le chiffre (ou groupe de bits) le moins significatif de chaque clef,
- trie la liste des éléments selon ce chiffre, mais conserve l'ordre des éléments ayant le même chiffre (ce qui est un tri stable).
- répète le tri avec chaque chiffre plus significatif.
[modifier] Exemple
Trier la liste : 170, 45, 75, 90, 2, 24, 802, 66
- tri par le chiffre le moins significatif (unités) :
170, 90, 2, 802, 24, 45, 75, 66
- tri par le chiffre suivant (dizaines) :
2, 802, 24, 45, 66, 170, 75, 90
- tri par le chiffre le plus significatif (centaines) :
2, 24, 45, 66, 75, 90, 170, 802
[modifier] Lien externe
- Démonstration et comparaison du tri par base (en) avec du JavaScript
