¿Qué es el algoritmo de Radix Sort?

Es un método de ordenamiento en el que se ordena los elementos de una lista procesando sus dígitos de forma individual.  Funciona clasificando los elementos según los valores de los dígitos de menor a mayor, primero en función del dígito menos significativo, luego en función del siguiente dígito más significativo, y así sucesivamente, hasta que todos los dígitos hayan sido considerados. 

Un aspecto importante a mencionar es que Radix Sort no esta solo limitado a enteros esto debido a que trata los elementos como caracteres lo que engloba  nombres,  fechas y números en punto flotante. 

Para el proceso de clasificación es necesario utilizar un algoritmo de ordenamiento estable, como el counting sort o el bucket sort. 

¿Cómo funciona ?    

El método de este algoritmo consiste en hacer motones como si de fichas se tratara,  una por cada digito estos montones posteriormente estos montones recogen en orden ascendente y se repite el proceso hasta terminar con el digito mas significativo.  

Los pasos son los siguientes: 

1. Obtención de la cantidad de dígitos máxima: Primero, se determina la cantidad máxima de dígitos presentes en los números de la lista. Esto se utiliza para determinar cuántas pasadas o "pasos" serán necesarios para ordenar completamente la lista.

2. Ordenamiento por cada dígito: Comenzando por el dígito menos significativo, se realiza un proceso de ordenamiento estable (como counting sort) en función de ese dígito para todos los elementos de la lista.

3. Repetición del proceso: Se repite el proceso de ordenamiento para cada dígito, desde el menos significativo hasta el más significativo. Cada vez que se ordena en función de un dígito, los elementos permanecen en el orden relativo que tenían antes de la clasificación, lo que garantiza que el ordenamiento sea estable.

4. Finalización: Después de ordenar según el dígito más significativo, la lista estará completamente ordenada.

Implementación en Python. 

Imagine que deseamos ordenar la siguiente lista:

                         3 | 5 |15 | 12 | 89 | 99  

El proceso seria el siguiente: 

El código en Python es:

def counting_sort(arr, exp):

    n = len(arr)  # Obtener la longitud de la lista
    output = [0] * n  # Crear una lista de salida del mismo tamaño que la lista original
    count = [0] * 10  # Crear una lista de conteo para los dígitos (0-9)

    # Contar la frecuencia de cada dígito en la lista
    for i in range(n):
        index = arr[i] // exp  # Calcular el índice del dígito actual
        count[index % 10] += 1  # Incrementar el conteo del dígito en la lista de conteo

    # Calcular las posiciones finales de los elementos en la lista de salida
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Construir la lista de salida en orden ascendente según el dígito actual
    i = n - 1

    while i >= 0:
        index = arr[i] // exp  # Calcular el índice del dígito actual
        output[count[index % 10] - 1] = arr[i]  # Colocar el elemento en la posición correcta en la lista de salida
        count[index % 10] -= 1  # Reducir el conteo del dígito
        i -= 1

    # Copiar los elementos ordenados de la lista de salida a la lista original
    for i in range(0, len(arr)):
        arr[i] = output[i]


def radix_sort(arr):
    max_num = max(arr)  # Obtener el número máximo en la lista
    exp = 1
    while max_num // exp > 0:

        counting_sort(arr, exp)  # Llamar al counting_sort para ordenar los elementos en base al dígito actual
        exp *= 10  # Mover al siguiente dígito hacia la izquierda

# Ejemplo de uso

arr = [3, 5, 15, 12, 89, 99]
print("Lista desordenada:", arr)
radix_sort(arr)
print("Lista ordenada:", arr)

Salida :

  Lista desordenada:  [3, 5, 15, 12, 89, 99]         
  Lista ordenada:        [3, 5, 12, 15, 89, 99]         

Ventajas y Desventajas.

Ventajas:

1. Estabilidad: Radix Sort es un algoritmo estable, lo que significa que conserva el orden relativo de los elementos con claves iguales. Esto es importante en situaciones donde se requiere mantener el orden relativo original de los elementos.

2. Eficiencia en tiempo lineal: Radix Sort tiene una complejidad de tiempo lineal O(n * k), donde "n" es el número de elementos en la lista y "k" es el número de dígitos (o letras, en el caso de datos alfabéticos) en los números. Esta complejidad lineal hace que Radix Sort sea eficiente para listas grandes, especialmente cuando el rango de valores es relativamente pequeño.

3. No requiere comparaciones directas: A diferencia de algunos otros algoritmos de ordenamiento, como QuickSort o MergeSort, Radix Sort no requiere comparaciones directas entre los elementos. En su lugar, clasifica los elementos basándose en los dígitos individuales o letras en posiciones específicas.

4. Eficiente para datos con un rango limitado: Radix Sort es particularmente eficiente cuando el rango de valores en la lista es limitado, ya que no tiene en cuenta el valor absoluto de los elementos, sino solo los dígitos individuales.

Desventajas:

1.Requiere memoria adicional: Radix Sort puede requerir memoria adicional para almacenar las cubetas (buckets) utilizadas en cada paso de clasificación, lo que puede ser una desventaja en sistemas con recursos limitados o cuando se trata de listas muy grandes.

2. Ineficiente para rangos muy amplios: Si el rango de valores en la lista es muy amplio en comparación con el número de elementos, Radix Sort puede ser menos eficiente debido a la necesidad de manejar un gran número de cubetas y dígitos.

3. No adecuado para todos los tipos de datos: Radix Sort es más adecuado para datos numéricos o alfabéticos donde se puede aplicar la noción de dígitos o letras en posiciones específicas. Para otros tipos de datos, como objetos complejos o cadenas de texto, Radix Sort no es aplicable.