Leyendo no se que en internet, lei mencionar algo sobre preguntas de entrevistas de trabajo, y mencionaron que siempre es bueno saber como funciona Quicksort. Por algun motivo, el algoritmo de ordenamiento que siempre recuerdo es Bubble sort, pero todos sabemos que no es el mejor. So decidi repasar y leer como funciona quicksort.
Para los que no recuerdan quicksort es simplemente hacer 3 listas con la lista principal [PRINCIPAL]. Estas listas se generan bajo un criterio bien sencillo. Elige un numero cualquiera del arreglo, la primera lista tendra todos los numeros menores a ese numero [MENORES]. La segunda lista tendra todos los numeros que sean de igual valor a ese numero [IGUALES], y la tercera los mayores [MAYORES].
Una vez que tienes estas 3 listas, el resultado de Quicksort es el siquiente (Donde ++ es concatenar una lista):
Quicksort([MENORES]) ++ [IGUALES] ++ Quicksort([MAYORES])
Como veras, el algoritmo es recursivo, y llegara el momento que no encuentres numeros menores, iguales o mayores, asi que cuando Quicksort recibe una lista de un solo elemento, devuelve ese elemento.
En python esto sale en 4 lineas con list comprehension, literalmente:
def qs(lista): if len(lista) <= 1: return lista p = lista[0] #el pivote return qs([x for x in lista if x < p]) + [x for x in lista if x == p] + qs([x for x in lista if x > p])
Pudieras aplicar este algoritmo a cualquier tipo de objeto en Python si para ese objeto defines las funciones de comparacion.
Demasiado arrecho, viva python.
PS: Despues de escribir esto, encontre una implementacion aun mas corta, en la que no utilizan list comprehension, utilizan
funciones lambda, en vez de hacer [x for x in lista if x < pivote] hacen filter(lambda x,y=pivote: x < y,lista), eso devuelve los elementos que cumplen con la funcion lambda en la lista, es decir filter(funcion, lista)
Una cosa es que se implante de manera sucinta, y otra es que siga siendo eficiente. Al implantar QuickSort con list-comprehensions en Python de esa manera tienes dos problemas:
1. Estás escogiendo como pivote el primer elemento y en general esa es una elección mala. Como mÃnimo se sugiere escoger el mediano entre tres elementos de la lista a procesar (primero, medio y último). Hay suficientes demostraciones matemáticas que comprueban que escoger el primer elemento es en general peor que entre tres, y suele llevarte al peor caso de QuickSort que es cuadrático.
2. Para filtrar la lista estás haciendo dos recorridos cada vez. Eso contribuye con una constante grande en el tiempo asintótico de corrida y perjudica más de lo que ayuda. Además, estás _copiando_ listas, porque la primera tiene que persistir y como Python no tiene evaluación perezosa ni listas “reusables”, consumes bastante más memoria de la que necesitas.
En un lenguaje como Haskell, que tiene evaluación perezosa y listas “reusables”, puede hacer el pivoteo en tiempo lineal con una sola pasada de manera muy sucinta también y sólo te queda el problema de escoger el pivote razonablemente.
Escoger “mal” el pivote, hace que QuickSort sea tan malo como cualquiera de los cuadráticos (Bubble, Insert o Select). En general, usar MergeSort o HeapSort suele ser mejor, especialmente si no sabes nada sobre la distribución de tus datos.