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