azrael

Yo soy de la creencia de que tiene que haber un algoritmo de ordenación mejor que Quicksort, un algoritmo que haga el numero imprescindible de comparaciones y ni una más.

Pero mientras no se me ocurra otro algoritmo, lo mejor que hay es Quicksort :P.

Una practica común es añadirle pequeñas optimizaciones a Quicksort, como que al trabajar con pocos elementos se use inserción o que si se detecta un caso malo se cambie a otro algoritmo (heapsort en el caso de introsort).

Otra posibilidad sería recorrer primero el vector de elementos, para comprobar si esta o no ordenado (en orden directo o inverso). De esta forma si no lo esta tendremos ya un “buen” pivote (el primer elemento no ordenado).

Esto añadirá posiblemente muchas comparaciones (máximo O(n)), así que no se si será practico, aunque el mejor caso sería O(n) (para vectores ordenados).

¿Y un algoritmo de ordenación que busque trozos ordenados (de forma directa o inversa) en el vector y luego los junte (a la mergesort)? Su peor caso sería n/2 vectores ordenados, de 2 elementos, a juntar. El mejor n-1 comparaciones para vectores ordenados.

Aprovechare la última practica de metodología de la programación para probar la eficiencia de versiones de todos estos algoritmos.

Desde el punto de vista de un programador de videojuegos, hacia aquí debería de ir un futuro lenguaje de programación. Miraros la presentación porque es muy sencillita e interesante. Curioso que en Haskell ordenar sea equivalente a Quicksort :p.

Explicándolo de forma sencilla; ordenar n datos es lo mismo que poner el dato mínimo en la posición inferior, el máximo en la posición superior y repetir el algoritmo para n-2 datos.

O lo que es lo mismo 1/2(n^2-n) = 1 + 2(n-1) + 1/2((n-2)^2-(n-2).

Tambien podría hacerse 1/2(n^2-n)= n-1 + 1/2((n-1)^2-(n-1)), que de hecho es el algoritmo de selección.

Así que he reinventado la rueda :P. El algoritmo es un cocktail sort por selección recursivo.

P.D.: ¿Pero a que queda bonito simétrico y recursivo?

Por fin he sacado un algoritmo en claro.

Creo que el tiempo es siempre 1/2(n^2-n) y fuerza mucho con la recursividad.

No es n log n, pero me ha parecido bonito. No sé si funcionará porque no consigo probarlo.

Si sabéis si hay alguno parecido avisadme.

—————————————————————-
procedure ordenar (T: in out tpLista)is
—————————————————————-
————————————————————-
procedure OrdenarIzda (T: in out Tplista)is
————————————————————-
aux:tpDato;
begin
if Numdatos(T)>1 then
if T(T’First)>T(T’Last) then–intercambia
Aux:=T(T’First);
T(T’First):=T(T’Last);
T(T´Last):=Aux;
end if;
if T’Last-T’First/=1 then
OrdenarIzda(T(T’First..T’Last-1));
end if;
end if;
end Ordenarizda;
————————————————————-
————————————————————-
procedure OrdenarDcha (T: in out Tplista)is
————————————————————-
aux:tpDato;
begin
if Numdatos(T)>1 then
if T(T’First)>T(T’Last) then–intercambia
Aux:=T(T’First);
T(T’First):=T(T’Last);
T(T´Last):=Aux;
end if;
if T’Last-T’First/=1 then
OrdenarDcha(T(T’First+1..T’Last));
end if;
end if;
end OrdenarDcha;
————————————————————-
aux:tpDato;
begin
if Numdatos(T)>1 then
if T(T’First)>T(T’Last) then–intercambia
Aux:=T(T’First);
T(T’First):=T(T’Last);
T(T´Last):=Aux;
end if;
if T’Last-T’First/=1 then
OrdenarIzda(T(T’First..T’Last-1));
Ordenar(T(T’First+1..T’Last-1));
OrdenarDcha(T(T’First+1..T’Last));
end if;
end if;
end ordenar;
—————————————————————

Vaya burradas he escrito estos días. Me salva que no estoy durmiendo lo suficiente.

Un árbol binario con n nodos (y no hojas) tiene una altura log n.

Por lo tanto el maravilloso método de ordenación al que le estaba dando vueltas no tendrá nunca complejidad n log n.

Tán sólo será un algoritmo de ordenación por burbuja optimizado, supongo que de coste medio 1/2(n^2-1) . El mejor caso sería como en ordenación por burbuja n. De todas formas si me da tiempo acabaré el algoritmo.

Sigo sin ver como es posible que con menos comparaciones se puedan ordenar n elementos, empiezo a pensar seriamente si no debería de haberme metido a letras.

EDIT: Sigo dándole vueltas a estas tonterías que parece, me superan.  No sé porque coño estaba hablando de árboles binarios cuando estaba hablando de combinaciones. Hasta hace un momento no me he dado cuenta de que no es lo mismo.

Definitivamente tengo que dormir más.(Que pesimista me ha salido el post.)

Aún puede ser que la idea que me rondaba la cabeza sea de alguna utilidad: una especie de Quicksort invertido.

Tirado en la cama este mediodía, me ha parecido dar con la “chispa” del n log n.

El árbol binario de n hojas tiene 1/2(n^2-n) nodos y una altura log n.

El árbol binario de n hojas tiene n-1 nodos y una altura log n-1. (No estaba pensando en árboles binarios sino en combinaciones.)

Por lo tanto un algoritmo de ordenación tendría complejidad log n si hiciera en cada iteración las comparaciones correspondientes a todo un nivel del árbol. Pero el numero de comparaciones en cada nivel del árbol depende de n.

Podríamos pensar que entonces la complejidad será de orden n log n… pero hay algo que no me cuadra. No tengo la cabeza para pensar, pero ¿la complejidad no sería 1/2(n^2-n) log n ? xD

Al final voy a tener que leer los libros de Knuth.

Llevo un par de días interesado en los algoritmos de ordenación por comparación.

Lo que ya esta claro es que generalmente el algoritmo más rápido conocido es el Quicksort.

¿Pero porqué?

Adelanto que en mis razonamientos falla algo.

Por un lado sabemos (porque eso dicen) que está demostrado que los algoritmos d ordenación por comparación tienen una complejidad mínima n log n (se deduce de log n!) .

Sin embargo, empezando por otro lado, yo no he llegado ahí.

Empecemos por que hay n elementos a ordenar. Entre esos elementos, el numero de relaciones de orden diferentes serán

1/2*(n^2-n). Y según entiendo yo, para estar seguro de tener todos los elementos ordenados, habrá que conocerlas todas, así que creo que eso debería de caracterizar el coste de los algoritmos (no es así). Otra cosa sería que decidiéramos confiar un poquito en el azar :P.

Sigamos.

Cualquiera de los algoritmos de ordenación que consiguen ordenar n elementos en n log n se basan en un árbol binario, ya sea de forma explicita (heapsort) o implicita (Quicksort).

Si consideramos un árbol binario de altura log n, cuyas hojas serían los n elementos, los nodos serían el numero de relaciones de orden diferentes, numero de iteraciones de un algoritmo ideal.

Me da la impresión que esto podría resolverse “desde arriba” (desde la raíz a las hojas) o “desde abajo” (desde las hojas hacia la raíz). Mis intentos de hacerlo desde abajo, fueron infructuosos, igual es imposible, pero creía que podría haber un algoritmo bastante sencillo que lo resolviera, sin necesidad de ir usando un pivote. Sin embargo, desde arriba es una interpretación del algoritmo Quicksort, haciendo uso de un pivote.

De ahí, buscando un algoritmo de ordenación optimo, me encontré con lo que creo que es una versión iterativa de Quicksort.

La idea, si no me equivoco, es; coges un pivote, comparas el resto de los n elementos con el pivote, y los vas situando a su izquierda y derecha, en función de la relación de orden, quitas el pivote de la ecuación, cojes otro pivote y repites la operación. Así hasta tener los n elementos ordenados.

Bueno, voy a ver si hago pruebas de eficiencia con la primera practica de Metodología del año pasado.

Si alguna mente más despierta me corrige en mis errores o me orienta un poquito en los porqués, estaría muy agradecido.

EDITO:1/2*(n^2-n) resulta ser simplemente el coste del algoritmo de ordenación por burbuja  optimizado.

Sigo sin entender gracias a que información un algoritmo de ordenación consigue ser más rápido que eso.