Quicksort

QUICKSORT.

El quicksort es popular porque no es difícil de implementar y proporciona muy buenos resultados generales (funciona bien en una amplia diversidad de situaciones) y en muchos casos consume menos recurso que cualquier otro método de ordenación.

El algoritmo fundamental es el siguiente:

*Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

*Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

*La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

*Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

*En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño.

*En el peor caso, el pivote termina en un extremo de la lista. El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas.

...