Algoritmos de ordenación.
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.
April 12th, 2007 at 22:12
una precisión: el quicksort es el más rápido en la práctica, pero su coste en caso peor es cuadrático (es nlogn en el caso promedio, pero n^2 en el peor caso); métodos nlogn en el caso peor son el heapsort y el mergesort
no sé si te han contado o has leído el porqué de la cota mínima nlogn para la ordenación por comparación de elementos… echa un vistazo a estas transparencias, por ejemplo
la idea es que si pongo en la raíz de un árbol mis n datos y hago una comparación entre dos de sus elementos, se generan dos subárboles (en uno están las permutaciones para las que la comparación es cierta y en el otro el resto); si repito lo mismo en cada nodo, obtengo un árbol en cuyas hojas están todas las permutaciones posibles de los n datos (n!); el peor caso para ordenar los datos coincide entonces con la altura del árbol; se puede demostrar fácil que la menor altura posible para un árbol con x hojas es log x, así que la menor altura posible para el árbol de las permutaciones es log(n!) y eso sale >= n/2 logn
bueno… todo está en los libros…
April 16th, 2007 at 15:50
Gracías por leer, Javifields.
En cuanto a lo que comentas, hoy mismo le he dado el coñazo a l profesor Fernando Tricas, porque no sabía esto que habías escrito. Así que gracias ;).
April 18th, 2007 at 00:01
Hay algo que no me queda muy claro según lo que propones.
¿Como asegura eso que no se pueden ordenar los elementos por comparación en menos de n/2 log n?
El recurso de utilizar un árbol para explicar la cota mínima me parece muy artificial (eso ya lo había visto usado, por ejemplo, está claro que puedes ordenar datos en n log n porque lo que cuesta introducir cada dato en un arbol binario es log n, y tienes n datos.).
¿No hay una explicación más “matemática” de la cota mínima del problema?
Igual esta es lo suficientemente formal.
Me interesé en los algoritmos de ordenación simplemente porque quería buscar alguna forma de derivar un algoritmo de la forma mas rápida de ordenar (aka buscar el algoritmo más eficiente que haga algo, probablemente imposible).
De hecho en este caso no parece imposible, el único problema sería hacer un árbol con n! nodos…
Intentaré repetir por mi cuenta el razonamiento.
April 18th, 2007 at 00:06
Me lo he replanteado y ya me convence.
En cada comparación hay sólo dos posibilidades, se cumple la condición o no. De hay que salga de forma natural un árbol.
¡Lo entiendo! xD
May 15th, 2007 at 20:16
Hola!
me puedes mandar la version iterativa del Quicksort para echarle un ojo y comentamos..
Gracias!!
August 26th, 2007 at 02:07
[...] Una pequeña discusión el la talk-page de sorting algoritms de Wikipedia, sobre un argumento que ya me dió Javifields en su día. [...]