🚀 go-pugleaf

El d�a Sun, 10 Jan 1999 02:01:42 +0100, JOSEP LARDIEZ YEGOLA
<xxxjly@redestb.es> escribi�:

>Estoy realizando un programa de clasificaci�n de elementos y deseo
>ordenarlos sin tener que usar un algoritmo de ordenaci�n cl�sico sino
>por c�lculo. Conozco el intervalo de valores que va de 0 a 2.000.000.
>Tengo como m�ximo 6000 elementos diferentes. Conozco los valores de los
>elementos dentro del intervalo. Luego parece f�cil, divido el valor del
>elemento por una constante (2000000/6000) y obtengo un valor entre 1 y
>6000. Pero existe un problema:

Eso que est�s haciendo no es otra cosa que una tabla hash, si no me
equivoco.

>        -Como debo tomar el valor entero del resultado, cuando varios
>elementos est�n muy juntos, este resultado tomar� valores id�nticos,
>aunque var�e su valor absoluto.

Y lo que acabas de describir es precisamente el problema de las
colisiones en una tabla hash.

>�C�mo podr�a realizar este proceso sin
>tener que recurrir a un algoritmo de ordenaci�n cl�sico tipo burbuja,
>etc?

Una posibilidad ser�a usar ese m�todo que describes para clasificar
los elementos en una serie de "clases", determinadas por ese valor
entero entre 1 y 6000 que t� est�s calculando, y luego aplicar un
algoritmo de ordenaci�n a cada una de las clases en las que haya m�s
de un elemento. Otro tema muy distinto es c�mo hacer eso de forma
eficiente.

Creo que te trae m�s cuenta utilizar directamente un algoritmo de
ordenaci�n, aunque teniendo en cuenta el n�mero de elementos, yo
usar�a quicksort, shellsort o similares, antes que uno tipo burbuja.

>Un sistema podr�a ser el recalcular los valores para distribuirlos
>uniformemente y luego aplicar el algoritmo anterior, pero hay que
>recordar que s�lo conozco los valores de los elementos y el n�mero de
>ellos pero no los tengo ordenados para realizar operaciones del estilo
>de hallar diferencias y recalcular valores.

Para redistribuir uniformemente los valores deber�as conocer antes su
distribuci�n previa, pero claro, calcular la funci�n distribuci�n y
redistribuir los valores uniformemente te va a salir
computacionalmente m�s complejo que ordenarlos directamente.

Salu2: GUILLE
----
Guillermo Rodriguez Garcia
<XXguille@XXiies.XXes>  (ya sabes :-)