Quiksorft

INTRODUCCIÓN
Uno de los problemas más frecuentes con los que se enfrentan los diseñadores de software, es la ordenación de una lista de elementos. Ya sea, que estés lidiando con una base de datos de direcciones Web, una lista de clientes o el listín telefónico de una ciudad, seguramente se necesitará ordenarlos de alguna forma para que esos datos sean útiles. Quicksort es el algoritmo deordenamiento más rápido del mundo, creado por el científico británico en computación C. A. R. Hoare basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional an log n.
No sólo encontró una forma muy ingeniosa para ordenar elementos, sino que además logró una demostración matemática que prueba que este sistema es en realidad el más rápidoposible, por lo que desde hace más de 50 años la discusión de que pasos conviene seguir para ordenar una lista ha dejado de tener sentido. La respuesta es siempre la misma: Quicksort. Antes de ver como hace su magia este algoritmo, tenemos que comprender un concepto muy utilizado por los informáticos llamado recursividad. La recursividad es la forma en la cual se especifica un proceso basado en su propiadefinición.  Para ponerlo más claro podemos ver un ejemplo: “la suma de los números de 1 a n es igual a la suma de 1 a (n-1) + n” En la frase anterior existe la recursividad. Se nos dice que para sumar una serie de números, basta con sumar el último de la lista a la suma de todos los anteriores.
Obviamente, para obtener esa suma parcial puede aplicarse el mismo procedimiento, una y otra vez,hasta llegar a una lista que solo contiene el “1”. La posibilidad de definir la solución de un problema recurriendo a la propia definición se llama recursividad. Es sumamente útil, aunque debe prestarse mucha atención para evitar que un pequeño error de programación nos atrape en un bucle infinito. En este trabajo nos centraremos en ShellSort. Describiremos la idea que subyace detrás del algoritmo,e intentaremos llegar de manera intuitiva al código del algoritmo.

Quicksorft: Algoritmo de ordenamiento rápido.
El secreto de Quicksort consiste en dividir la lista original en dos listas más pequeñas. Para ello, se elige un elemento cualquiera (aunque en general se suele utilizar el que se encuentra en medio de la lista) que nos servirá como pivote. Luego se recorre toda la lista, con elobjeto de colocar los elementos más pequeños que el pivote a la izquierda del mismo, y los mayores a la derecha. Las implementaciones más eficientes realizan esta tarea a la vez, recorriendo simultáneamente la lista en ambas direcciones e intercambiando entre sí cada par de elementos “descolocados” que se encuentran a su paso. Culminada esta etapa tenemos un grupo de elementos menores que el pivote,el pivote, y otro grupo compuesto por números mayores a él.
En este punto es donde juega un papel importante la recursividad: si cada uno de esos grupos vuelve a dividirse en dos y se aplica lo explicado anteriormente de forma recursiva, tenemos resuelto el problema. Lo mejor de todo es que el tamaño de las sablistas y por ende el tiempo que se necesita para procesarlas es cada vez menor.  Encada nivel el tamaño de las sub listas la mitad del anterior, lo que permite ordenar una lista de 1024 elementos en 10 “pasadas”, y una de más de un millón en solo 20. Y lo mejor de todo es que no requiere de una “segunda caja vacía” sobre la que ordenar los elementos, con lo que el consumo de recursos (memoria) es menor.
Otra innegable ventaja del algoritmo Quicksort es que puedeser paralelizado. ¿Que significa esto? Que en ordenadores con más de un microprocesador algo muy común en los superordenadores que, justamente, son los que suelen realizar procesos como estos con cantidades enormes de elementos- el problema puede dividirse en muchas partes pequeñas y cada una ser resuelta por una CPU diferente. Esta característica también es importante cuando el número de elementos es tan...