Algoritmo QuickSort

Introducción y Descripción del Algoritmo

Éste algoritmo se basa en el principio de divide y conquistarás. Resulta más fácil ordenar listas pequeñas que una grande, con lo cual irá descomponiendo la lista en dos partes y ordenando esas partes.

Para ésto utiliza la recursividad.

• Dada una lista, elegir uno de sus elementos, que llamamos pivot
• Dividir la lista en dos sublistas:
  • una con los elementos "menores"
  • otra con los elementos "mayores"
• Ordenar recursívamente ambas sublistas
• Armar la lista resultado como: menoresOrdenados + pivot + mayoresOrdenados

Vamos a ver más adelante que la elección del pivot y el orden con el que venga ya de entrada la linea podrá afectar la eficiencia del algoritmo. En principio el algoritmo no especifica cómo elegir el pivot.

Ejemplo Paso a Paso

Veamos un ejemplo para ordenar la siguiente lista:

[ 42, 124, 23, 5, 89, -1, 44, 643, 34]

En nuestro ejemplo vamos a seleccionar el primer elemento de la lista como el pivot.

Veamos entonces, paso a paso se va a ir formando este árbol de llamados recursivos. En rojo mostramos el pivot. A izquierda las sublistas menores, y a la derecha la de los mayores.

En verde están los nodos "caso base", es decir lista de un único elemento o bien lista vacía.

Entonces estos nodos se van a resolver fácil y se van a concatenar con los pivots de arriba. Así empezamos a volver en los llamados recursivos.

Si sacamos las listas originales de cada nodo y solo dejamos los pivots, queda más claro:

Ya tenemos todo el tercer nivel resuelto así que cada par va a retornar para concatenarse entre sí con el pivot en el medio.

Ya casi estamos. Tenemos dos listas ordenadas, la de los menores y la de los mayores, y el primer pivot. Concatenamos y eso nos da el resultado final:

Implementación

Acá podemos ver una implementación en Python del algoritmo:

def quicksort(lista):

    return lista if len(lista) <= 1 else innerquicksort(lista[0], lista[1:])

def innerquicksort(pivot, resto):

    # menores_ordenados + pivot + mayores_ordenados

    return filtradosOrdenados(pivot, resto, less) + [pivot] + filtradosOrdenados(pivot, resto, greater);

def filtradosOrdenados(pivot, lista, condition):

    return quicksort([i for i in lista if condition(i, pivot)])

Veamos un par de cosas:

• El algoritmo está dividido en 3 funciones.
• quicksort:
  • la función principal (en cuanto a que la llama quien quiere ordenar)
  • solo implementa el checkeo por el caso base, el caso recursivo lo delega en otra función innerquicksort préviamente seleccionando el pivot.
• innerquicksort:
  • recibe ya el pivot y el resto de la lista.
  • Es la que arma la lista resultado entre la sublista de menors + pivot + sublista de mayores
  • Para crear y ordenar las sublistas delega en filtradosOrdenados, pasándole diferentes funciones como parámetros (less y greater que dicen si el primer elemento es menor o mayor que el segundo, respectivamente)
• filtradosOrdenados:
  • Es una función de orden superior que dada una lista, un pivot y una función booleana (parecido a un filter)
    • filtra la lista si la función se cumple para los elementos y el pivot (es decir que se ejecuta la función por cada elemento comparando contra el pivot)
    • llama a quicksort nuevamente con la lista filtrada. Acá está la recursividad.
  • Conceptualmente lo que hace esto es filtrar para quedarse con los menores/mayores y a esa sublista mandarla a ordenar recursívamente.

Análisis del Algoritmo

Al igual que el mergesort este algoritmo tiene tiempo "promedio" dado por orden O(n log n).

Sin embargo la eficiencia va a depender del pivot seleccionado. Veamos un ejemplos.

Extremos como Pivot

Veamos qué sucedería si continuando con la estrategia de seleccionar el primer elemento como pivot, los mismo números del ejemplo anterior hubieran llegado ordenados de esta otra manera:

[ -1, 643, 124, 5, 23, 89, 44, 34, 42 ]

Veamos el árbol de invocaciones recursivas y las sublistas:

Lo que sucedió acá es que los elementos estaban ordenados de cierta forma en que siempre el primero de cada sublista o bien era el máximo, o bien era el mínimo, entonces nunca pudimos dividir en mitades más o menos iguales. Siempre generamos una sublista vacía y otra con todos los elementos.

En este caso, al igual que si la lista ya viene ordenada, la eficiencia del algoritmo se degrada bastante al orden O(n²)