Tri radix
Dernière mise à jour
Le tri radix est un tri sans comparaison pour les entiers. Au lieu de comparer les valeurs, il trie les nombres chiffre par chiffre. La version du chiffre le moins significatif (LSD) traite d'abord le chiffre des unités, puis des dizaines, puis des centaines, en utilisant un tri par comptage stable à chaque chiffre. Comme chaque passe est stable, une fois le chiffre le plus significatif traité, tout le tableau est trié. Appuyez sur lecture ci-dessus pour voir chaque passe de chiffre réorganiser les barres.
Le tri radix s'exécute en temps O(d·(n + k)), où d est le nombre de chiffres et k la base (10 ici). Pour des entiers de largeur fixe, c'est quasiment linéaire - il peut battre les tris par comparaison en O(n log n) - mais il ne fonctionne que sur des données décomposables en chiffres ou en clés.
Complexité temporelle et spatiale
| Cas | Complexité | Notes |
|---|---|---|
| Temps | O(d·(n + k)) | d chiffres, base k (linéaire pour d fixe) |
| Espace | O(n + k) | Tableau de sortie + comptages de chiffres |
| Stable | Oui | Chaque passe de chiffre est un tri par comptage stable |
| Comparaison ? | Non | Trie par chiffre, sans comparer les valeurs |
| Fonctionne sur | Entiers/clés | Pas sur des objets comparables généraux |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Trouver la valeur maximale pour connaître le nombre de chiffres à traiter. |
| 2 | Commencer par le chiffre le moins significatif (les unités). |
| 3 | Trier le tableau de façon stable selon ce chiffre avec un tri par comptage. |
| 4 | Passer au chiffre plus significatif suivant. |
| 5 | Répéter jusqu'à traiter toutes les positions de chiffres. |
Exemple détaillé
Tri de [170, 45, 75, 90, 2, 24, 66] :
| Passe | Tableau | Action |
|---|---|---|
| Début | [170, 45, 75, 90, 2, 24, 66] | Le maximum est 170, donc trois passes de chiffres sont nécessaires. |
| Unités | [170, 90, 2, 24, 45, 75, 66] | Tri stable selon le chiffre des unités : 0, 0, 2, 4, 5, 5, 6. |
| Dizaines | [2, 24, 45, 66, 170, 75, 90] | Tri stable selon le chiffre des dizaines : 0, 2, 4, 6, 7, 7, 9 (170 garde son avance sur 75). |
| Centaines | [2, 24, 45, 66, 75, 90, 170] | Tri stable selon le chiffre des centaines ; seul 170 a un 1, il passe donc en dernier. Trié. |
Quand utiliser le tri radix
| À utiliser quand | À éviter quand |
|---|---|
| Les clés sont des entiers ou des chaînes de longueur fixe que vous pouvez découper en chiffres. | Vous devez trier des objets arbitraires avec un comparateur personnalisé. |
Les clés ont un nombre de chiffres d petit et borné, si bien que O(d·(n + k)) bat O(n log n). | Les clés sont très longues ou non bornées, rendant d grand et les passes coûteuses. |
Vous avez besoin d'un tri stable et pouvez vous permettre O(n + k) d'espace supplémentaire. | La mémoire est limitée et les tampons O(n + k) sont inacceptables. |
La plage de valeurs ou la base k est modérée par rapport à n. | k est énorme, de sorte que chaque passe de tri par comptage domine le temps d'exécution. |
Code de Radix Sort
Une implémentation propre et exécutable de Radix Sort en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Radix Sort en Python
Python
1def radix_sort(a):2 # Sort by each decimal digit, least significant first3 max_value = max(a)4 exp = 15 while max_value // exp > 0:6 a = sort_by_digit(a, exp)7 exp *= 108 return a9
10
11def sort_by_digit(a, exp):12 buckets = [[] for _ in range(10)]13 for value in a:14 digit = (value // exp) % 1015 buckets[digit].append(value)16 # Concatenating buckets 0..9 keeps the sort stable17 return [value for bucket in buckets for value in bucket]18
19
20nums = [170, 45, 75, 90, 802, 24, 2, 66]21print("Before:", nums)22print("After: ", radix_sort(nums))Code de Radix Sort en JavaScript
JavaScript
1function radixSort(arr) {2 let a = [...arr];3 const max = Math.max(...a);4 // One counting pass per digit, least significant first5 for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {6 const buckets = Array.from({ length: 10 }, () => []);7 for (const x of a) {8 buckets[Math.floor(x / exp) % 10].push(x);9 }10 a = buckets.flat();11 }12 return a;13}14
15const data = [170, 45, 75, 90, 802, 24, 2, 66];16console.log("Before:", data);17console.log("Sorted:", radixSort(data));Code de Radix Sort en Java
Java
1import java.util.Arrays;2
3public class Main {4 static void radixSort(int[] arr) {5 int max = 0;6 for (int v : arr) max = Math.max(max, v);7 // One stable counting pass per decimal digit8 for (int exp = 1; max / exp > 0; exp *= 10) countingPass(arr, exp);9 }10
11 static void countingPass(int[] arr, int exp) {12 int n = arr.length;13 int[] out = new int[n];14 int[] count = new int[10];15 for (int v : arr) count[(v / exp) % 10]++;16 for (int i = 1; i < 10; i++) count[i] += count[i - 1];17 // Walk backwards to keep the pass stable18 for (int i = n - 1; i >= 0; i--) {19 int digit = (arr[i] / exp) % 10;20 out[--count[digit]] = arr[i];21 }22 System.arraycopy(out, 0, arr, 0, n);23 }24
25 public static void main(String[] args) {26 int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};27 System.out.println("Before: " + Arrays.toString(arr));28 radixSort(arr);29 System.out.println("After: " + Arrays.toString(arr));30 }31}Code de Radix Sort en C++
C++
1#include <algorithm>2#include <iostream>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)11void countingPass(std::vector<int>& a, int exp) {12 std::vector<int> output(a.size());13 std::vector<int> count(10, 0);14 for (int x : a) ++count[(x / exp) % 10];15 for (int d = 1; d < 10; ++d) count[d] += count[d - 1];16 for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {17 int digit = (a[i] / exp) % 10;18 output[--count[digit]] = a[i];19 }20 a = output;21}22
23void radixSort(std::vector<int>& a) {24 int maxVal = *std::max_element(a.begin(), a.end());25 for (int exp = 1; maxVal / exp > 0; exp *= 10) {26 countingPass(a, exp);27 }28}29
30int main() {31 std::vector<int> data = {170, 45, 75, 90, 802, 24, 2, 66};32 std::cout << "Before: ";33 printVec(data);34 radixSort(data);35 std::cout << "After: ";36 printVec(data);37 return 0;38}Code de Radix Sort en C
C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)10void countingPass(int a[], int n, int exp) {11 int* output = malloc(n * sizeof(int));12 int count[10] = {0};13 for (int i = 0; i < n; i++) count[(a[i] / exp) % 10]++;14 for (int d = 1; d < 10; d++) count[d] += count[d - 1];15 for (int i = n - 1; i >= 0; i--) {16 int digit = (a[i] / exp) % 10;17 output[--count[digit]] = a[i];18 }19 for (int i = 0; i < n; i++) a[i] = output[i];20 free(output);21}22
23void radixSort(int a[], int n) {24 int maxVal = a[0];25 for (int i = 1; i < n; i++) {26 if (a[i] > maxVal) maxVal = a[i];27 }28 for (int exp = 1; maxVal / exp > 0; exp *= 10) {29 countingPass(a, n, exp);30 }31}32
33int main(void) {34 int data[] = {170, 45, 75, 90, 802, 24, 2, 66};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 radixSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}FAQ sur le tri radix
Quelle est la complexité temporelle du tri radix ?
Le tri radix est en
O(d·(n + k)), où d est le nombre de chiffres et k la base. Pour des entiers de largeur fixe, c'est quasiment O(n), ce qui peut être plus rapide que les tris par comparaison. Il utilise O(n + k) d'espace supplémentaire.Le tri radix est-il stable ?
Oui. Le tri radix LSD repose sur un tri par comptage stable à chaque chiffre ; c'est cette stabilité qui permet à l'approche chiffre par chiffre de produire un résultat correctement trié.
Quand puis-je utiliser le tri radix ?
Le tri radix fonctionne sur des données décomposables en chiffres ou en clés de taille fixe, comme des entiers ou des chaînes de longueur fixe. Ce n'est pas un tri par comparaison générique, il ne peut donc pas trier des objets arbitraires avec un comparateur personnalisé.
En quoi le tri radix diffère-t-il du tri par comptage ?
Le tri par comptage trie selon une seule clé en une passe et nécessite un tableau de comptage aussi grand que la plage de valeurs, ce qui le dégrade quand les valeurs sont dispersées. Le tri radix applique le tri par comptage chiffre par chiffre, gardant petit le tableau de comptage de chaque passe (base
k), ce qui lui permet de gérer de grandes plages de valeurs que le tri par comptage simple ne pourrait pas.Pourquoi le tri radix LSD commence-t-il par le chiffre le moins significatif ?
Commencer par le chiffre le moins significatif permet à chaque passe stable de préserver l'ordre établi par tous les chiffres moins significatifs précédents. Lorsque le chiffre le plus significatif est traité, les égalités sur ce chiffre sont déjà correctement ordonnées par les chiffres inférieurs, si bien que le tableau finit entièrement trié. Trier d'abord par le chiffre le plus significatif briserait cela et exigerait une approche récursive différente (tri radix MSD).
Le tri radix peut-il gérer les nombres négatifs ?
Pas directement - l'extraction de chiffres de base suppose des entiers non négatifs. Les correctifs courants consistent à décaler toutes les valeurs en ajoutant le minimum pour que tout soit non négatif, ou à trier séparément les négatifs et les non-négatifs puis à les concaténer. Ignorer cela est un bug fréquent lorsqu'on applique le tri radix à des données réelles.
Ressources associées
Plus de visualisations
