1

Bien pues estoy intentando aplicar el algoritmo Radix Sort en Python y necesito contar la cantidad de comparaciones y de pasos o intercambios que hace el algoritmo para organizar cierto vector. Tengo el problema de que los pasos siempre son iguales al número de comparaciones cuando no debería ser así y no sé cómo puedo solucionarlo agradecería mucho cualquier sugerencia o corrección.

Este es mi código, cabe mencionar que no uso ningún tipo de función.

arr = [3, 1, 5, 7, 6, 13, 20, 19, 22, 24, 29, 25, 32, 35, 39, 37, 36, 41, 43, 42, 44, 50, 46, 49, 45, 51, 53, 54, 57, 56, 55, 58, 61, 67, 64, 69, 71, 81, 77, 78, 73, 87, 99, 88, 89, 91, 90, 96, 97, 98]

max_num = max(arr)
exp = 1
n = len(arr)
comparaciones = 0 
pasos = 0  

while max_num // exp > 0:
     count = [0] * 10
     output = [0] * n

for i in range(n):
    index = arr[i] // exp
    count[index % 10] += 1

for i in range(1, 10):
    count[i] += count[i - 1]

i = n - 1

while i >= 0:
    index = arr[i] // exp
    output[count[index % 10] - 1] = arr[i]
    count[index % 10] -= 1
    i -= 1
    comparaciones += 1  

for i in range(n):
    arr[i] = output[i] 
    pasos += 1

exp *= 10

print("Arreglo ordenado:")
print(arr)
print("Comparaciones:", comparaciones)
print("Pasos:", pasos)

1 respuesta 1

0

Radix no hace comparaciones, si observas, no hay ni un solo if en todo el código.

En esta línea es que se hacen los intercambios:

output[count[index % 10] - 1] = arr[i]

Sin embargo, no le importa si el elemento actual es el mismo con el que se va a "intercambiar", simplemente lo sobreescribe sin más. Entonces la cantidad de pasos será cantidad de digitos de max(arr) y la cantidad de intercambios: len(arr) * cantidad_pasos

El código está "bien", pero mal indentado. Debe ser:

max_num = max(arr)
exp = 1
n = len(arr)
comparaciones = 0 # <-- Intercambios
pasos = 0  

while max_num // exp > 0:
    count = [0] * 10
    output = [0] * n

    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
        comparaciones += 1  

    for i in range(n):
        arr[i] = output[i]
    
    pasos += 1
    exp *= 10

print("Arreglo ordenado:")
print(arr)
print("Comparaciones:", comparaciones)
print("Pasos:", pasos)

El resultado es:

Arreglo ordenado:
[1, 3, 5, 6, 7, 13, 19, 20, 22, ...., 98, 99 ]
Comparaciones: 100
Pasos: 2
1
  • Muchas gracias por aclarar la situación, sin embargo, entonces según el resultado el algoritmo haría 100 intercambios y solo dos comparaciones o como debe ser? Commented el 28 sept. 2023 a las 21:01

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.