Ordenamiento rápido | Quicksort
Repo: https://github.com/umarquez/100DaysOfC0D3/tree/master/12-quicksort
Se trata de un algoritmo de ordenamiento que en promedio es del tipo O(nlog n ), pudiendo llegar a ser O(n²) en el peor de los casos; este funciona dividiendo la lista en dos a partir de un elemento pivote con el fin de colocar los elementos menores a este en el extremo izquierdo y los elementos mayores en el extremo derecho, ambos extremos se procesan de la misma manera de forma recursiva y se concatenan los resultados de la forma:
<lista izquierda> + <pivote> + <lista derecha>
Para cada lista a procesar se deben considerar los siguientes puntos:
- Si la lista se encuentra en el orden inverso al deseado se tratará del peor de los casos y tomará la mayor cantidad de pasos posibles en ser procesada, en este caso deberemos retornar la lista en el orden inverso al recibido sin realizar cada paso del algoritmo.
- Si la lista contiene 1 o menos elementos no requiere ser ordenada por lo que la retornamos tal cual la hemos recibido.
- Si la lista contiene 2 elementos, validamos que el primero sea menor o igual al segundo, los intercambiamos en caso necesario y los retornamos.
- A partir de 3 elementos podemos realizar la división eligiendo un valor cualquiera de la lista como pivote y enviando las lista no vacías a la misma función.
Ejemplo
Tenemos la siguiente lista que trataremos de ordenar:
Selección de pivote
En este caso, el elemento del medio es tomado como pivote.
Reordenamiento
Colocamos cada elemento a cada lado de la lista, según corresponda, una vez hecho esto, el elemento pivote se encontrará en su posición final; seleccionamos un nuevo pivote de cada lado y continuamos.
Procesamiento recursivo de la primer sub-lista
Procesamiento recursivo de la segunda sub-lista
Resultado final
Finalmente cada resultado se concatena y genera la lista ordenada final.
Implementación en Go
https://play.golang.org/p/PVDdjlvHqtd
