Complejidad Temporal
Mejor: O(d × (n + k))
Prom: O(d × (n + k))
Peor: O(d × (n + k))
Radix Sort ordena números dígito a dígito, desde el dígito menos significativo al más significativo (LSD Radix Sort). Usa un ordenamiento estable (como Counting Sort) como subrutina.
Cómo funciona:
1. Encontrar el número máximo para determinar la cantidad de dígitos
2. Para cada posición de dígito (unidades, decenas, centenas, ...):
a. Ordenar el arreglo basándose en el dígito actual usando un ordenamiento estable
3. Después de procesar todos los dígitos, el arreglo está ordenado
Complejidad Temporal:
Mejor: O(d × (n + k))
Promedio: O(d × (n + k))
Peor: O(d × (n + k))
donde d = número de dígitos, k = base (10 para decimal)
Complejidad Espacial: O(n + k)
Propiedades:
- Ordenamiento estable
- No es in-place
- No basado en comparaciones
- Eficiente para enteros y cadenas
Radix Sort puede superar a los ordenamientos basados en comparaciones cuando el número de dígitos es pequeño respecto a log(n).
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Radix Sort (Ordenamiento por Base)?
- Radix Sort ordena números dígito a dígito, desde el dígito menos significativo al más significativo (LSD Radix Sort). Usa un ordenamiento estable (como Counting Sort) como subrutina.
- ¿Cuál es la complejidad de Radix Sort (Ordenamiento por Base)?
- Tiempo (promedio): O(d × (n + k)) · Espacio: O(n + k)
- ¿Para quién es este visualizador de Radix Sort (Ordenamiento por Base)?
- La visualización de Radix Sort (Ordenamiento por Base) está pensada para nivel intermedio, dentro de la categoría Ordenamiento. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Radix Sort (Ordenamiento por Base)?
- En la misma categoría (Ordenamiento) puedes explorar: Bubble Sort, Selection Sort, Insertion Sort. Todos tienen visualización interactiva.