azrael

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.

Hoy me he encontrado a Mariano Rajoy por Zaragoza.

Al rato, y a pocos metros, estaba yo ayudando a cruzar un paso de cebra a una ancianita.

No ha sido hasta llegar a casa que me pregunto lo que habría dado el susodicho por hacerse la foto si hubiera visto a la ancianita primero.

Lo que si que me he preguntado toda la tarde (entre otras cosas), es que le hubiese dicho yo a Marianico.

Supongo que lo mejor habría sido sacar de mi todas mis raices mañas, llegar, darle un abrazo y preguntarle a voz en grito que coño hace inventandose chorradas en vez de hacer politica de verdad, o salvar el mundo o lo que sea.

Por mi que juegue al Tetris, pero que haga algo que sea bueno para alguien (me sirve el mismo).