ejercicio de ordenamiento

[Miguel Lederkremer]

Hola, estoy intentando resolver este ejercicio de final:

Implementar un algoritmo que permita ordenar un arreglo de n números cuyos valores van de 0 a n2−1 en tiempo lineal. Ayuda: Para resolver este problema, no es conveniente ver los números necesariamente en base 10.  

Todo apunta a que hay q usar radix sort con los números en binario

La complejidad es O( d*(k+n) )   

donde 

k rango de los dígitos: 2
d cant de dígitos: log2 n

entonces la complejidad me queda n log n

que estoy haciendo mal? se te ocurre como ordenarlo en tiempo lineal?

abrazo

Migue

[Miguel Lederkremer]

Perdón, el mensaje anterior era para un compañero. Igual ya encontré una solución, como cada elemento se puede escribir como n2−1  solo se trata de ubicar cada elemento en la posición n del arreglo ordenado
saludos!

 

def ordenar(arr):
    n = len(arr)
    ordenado = [None] * n
    for elem in arr:
        indice = int(math.sqrt(elem+1))-1
        ordenado[indice] = elem
    return ordenado

[Martín Buchwald]

Hola Miguel, 

Si lo resolvés en base 2 empeorás la situación porque vas a tener más dígitos para aplicar. 

Usar Countingsort no resuelve, porque no dice que sean de esa forma, sino que ese es el rango. 

--
Cómo usar esta lista: https://tiny.cc/algo2-lista-doc
---
Has recibido este mensaje porque estás suscrito al grupo "fiuba-7541rw-alu" de Grupos de Google.
Para cancelar la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a fiuba-7541rw-a...@googlegroups.com.
Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/fiuba-7541rw-alu/CAMJUqkCPn%3DXV7dhUm64i3T%3DZHFP-4wabp6ePk-4bAitLaS-%3DOA%40mail.gmail.com.

[Martín Buchwald]

Aclaro: pensar en ese "cambio de base" es lo correcto, pero no a base 2. 

[Miguel Lederkremer]

Gracias Martín, haciendo radix sort en base 16:

 

La complejidad es O( d*(k+n) ) donde:

n tamaño del arreglo

k rango de los dígitos: 16

d cant de dígitos: log16 (n 2 - 1) ≈ log16 (n 2) = 2 * log16 n ≈ log n

queda:

O( d * (k+n)  ) = O( log n * (16+n) ) ≈ O (n log n)

no es lineal como pide la consigna, donde está mi error?

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/fiuba-7541rw-alu/CABHe%3D7JtUH6n4Lbh802FKafrqvaF9EU00cfn9XyOM_Wy8PJ0HQ%40mail.gmail.com.

[Martín Buchwald]

El sáb., 5 sept. 2020 a las 12:38, Miguel Lederkremer (<mleder...@gmail.com>) escribió:

Gracias Martín, haciendo radix sort en base 16:

 

La complejidad es O( d*(k+n) ) donde:

n tamaño del arreglo

k rango de los dígitos: 16

d cant de dígitos: log16 (n 2 - 1) ≈ log16 (n 2) = 2 * log16 n ≈ log n

queda:

O( d * (k+n)  ) = O( log n * (16+n) ) ≈ O (n log n)

no es lineal como pide la consigna, donde está mi error?

Porque 16 tampoco es un valor correcto dados los valores de la consigna. Más allá que reduzca del caso de base 10, el problema va a persistir. 

 

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/fiuba-7541rw-alu/CAMJUqkBXEDBMngsJQMByhc5ZTB2kj5C2%2BfZye1%2BOEHqCU_UJSQ%40mail.gmail.com.