algorithm
Tri de radix
Recherche…
Informations de base sur le tri Radix
Radix Sort est un algorithme basé sur la comparaison des limites inférieures. C'est un algorithme de tri d'entiers non comparatif qui trie les données avec des clés entières en regroupant les clés par des chiffres individuels qui partagent une position et une valeur significatives. Le tri par radix est un algorithme de tri temporel linéaire qui trie le temps O (n + k) lorsque les éléments sont compris entre 1 et k. L'idée du tri de Radix est de faire un tri par chiffres en partant du chiffre le moins significatif au chiffre le plus significatif. Le tri par radix utilise le tri par comptage comme un sous-programme à trier. Le tri par radix est une généralisation du type de godet.
Pseudo code pour Bucket Sort:
- Créez un tableau d'éléments [0..n-1].
- Appeler un seau Trier de manière répétée sur les chiffres les moins significatifs de chaque élément en tant que clé.
- Renvoie le tableau trié.
Exemple de tri de Radix:
Espace auxiliaire: O(n)
Complexité temporelle: O(n)
