Radix Sort
Última actualización
Radix sort es un ordenamiento sin comparaciones para enteros. En lugar de comparar valores, ordena los números dígito a dígito. La versión de dígito menos significativo (LSD) procesa primero el dígito de las unidades, luego las decenas y después las centenas, usando un counting sort estable en cada dígito. Como cada pasada es estable, una vez procesado el dígito más significativo todo el arreglo queda ordenado. Pulsa reproducir arriba para ver cómo cada pasada de dígitos reordena las barras.
Radix sort se ejecuta en tiempo O(d·(n + k)), donde d es el número de dígitos y k es la base (10 aquí). Para enteros de ancho fijo esto es prácticamente lineal - puede superar a los ordenamientos por comparación O(n log n) - pero solo funciona con datos que puedan descomponerse en dígitos o claves.
Complejidad temporal y espacial
| Caso | Complejidad | Notas |
|---|---|---|
| Tiempo | O(d·(n + k)) | d dígitos, base k (lineal para d fijo) |
| Espacio | O(n + k) | Arreglo de salida + conteos de dígitos |
| Estable | Sí | Cada pasada de dígito es un counting sort estable |
| ¿Comparación? | No | Ordena por dígito, no comparando valores |
| Funciona con | Enteros/claves | No con objetos comparables generales |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | Encontrar el valor máximo para saber cuántos dígitos procesar. |
| 2 | Empezar por el dígito menos significativo (las unidades). |
| 3 | Ordenar el arreglo de forma estable por ese dígito con counting sort. |
| 4 | Pasar al siguiente dígito más significativo. |
| 5 | Repetir hasta procesar todas las posiciones de dígitos. |
Ejemplo resuelto
Ordenando [170, 45, 75, 90, 2, 24, 66]:
| Pasada | Arreglo | Acción |
|---|---|---|
| Inicio | [170, 45, 75, 90, 2, 24, 66] | El máximo es 170, así que se necesitan tres pasadas de dígitos. |
| Unidades | [170, 90, 2, 24, 45, 75, 66] | Orden estable por el dígito de las unidades: 0, 0, 2, 4, 5, 5, 6. |
| Decenas | [2, 24, 45, 66, 170, 75, 90] | Orden estable por el dígito de las decenas: 0, 2, 4, 6, 7, 7, 9 (170 conserva su ventaja sobre 75). |
| Centenas | [2, 24, 45, 66, 75, 90, 170] | Orden estable por el dígito de las centenas; solo 170 tiene un 1, así que va al final. Ordenado. |
Cuándo usar radix sort
| Úsalo cuando | Evítalo cuando |
|---|---|
| Las claves son enteros o cadenas de longitud fija que puedes dividir en dígitos. | Debes ordenar objetos arbitrarios con un comparador personalizado. |
Las claves tienen un número pequeño y acotado de dígitos d, de modo que O(d·(n + k)) supera a O(n log n). | Las claves son muy largas o no acotadas, lo que hace d grande y las pasadas costosas. |
Necesitas un orden estable y puedes permitirte O(n + k) de espacio extra. | La memoria es escasa y los búferes O(n + k) son inaceptables. |
El rango de valores o la base k es modesto respecto a n. | k es enorme, así que cada pasada de counting sort domina el tiempo de ejecución. |
Código de Radix Sort
Una implementación limpia y ejecutable de Radix Sort en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código 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))Código 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));Código 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}Código 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}Código 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}Preguntas frecuentes sobre Radix Sort
¿Cuál es la complejidad temporal de radix sort?
Radix sort es
O(d·(n + k)), donde d es el número de dígitos y k la base. Para enteros de ancho fijo esto es prácticamente O(n), lo que puede ser más rápido que los ordenamientos por comparación. Usa O(n + k) de espacio extra.¿Es estable radix sort?
Sí. El radix sort LSD se apoya en un counting sort estable en cada dígito; la estabilidad es lo que hace que el enfoque dígito a dígito produzca un resultado correctamente ordenado.
¿Cuándo puedo usar radix sort?
Radix sort funciona con datos que pueden descomponerse en dígitos o claves de tamaño fijo, como enteros o cadenas de longitud fija. No es un ordenamiento por comparación de propósito general, por lo que no puede ordenar objetos arbitrarios con un comparador personalizado.
¿En qué se diferencia radix sort de counting sort?
Counting sort ordena por una sola clave en una pasada y necesita un arreglo de conteo tan grande como el rango de valores, por lo que se degrada cuando los valores están muy dispersos. Radix sort aplica counting sort dígito a dígito, manteniendo pequeño el arreglo de conteo de cada pasada (base
k), lo que le permite manejar rangos de valores grandes que el counting sort simple no podría.¿Por qué el radix sort LSD empieza por el dígito menos significativo?
Empezar por el dígito menos significativo permite que cada pasada estable conserve el orden establecido por todos los dígitos anteriores menos significativos. Cuando se procesa el dígito más significativo, los empates en ese dígito ya están correctamente ordenados por los dígitos inferiores, así que el arreglo queda totalmente ordenado. Ordenar primero por el dígito más significativo rompería esto y requeriría un enfoque recursivo distinto (radix sort MSD).
¿Puede radix sort manejar números negativos?
No directamente: la extracción básica de dígitos supone enteros no negativos. Soluciones comunes son desplazar todos los valores sumando el mínimo para que todo sea no negativo, u ordenar por separado los negativos y los no negativos y luego concatenarlos. Ignorar esto es un error frecuente al aplicar radix sort a datos reales.
Recursos relacionados
Más visualizaciones
