Algoritmo Quicksort y como implementarlo en Python

QuickSort es un algoritmo de ordenamiento eficiente que utiliza un enfoque de “divide y vencerás” para ordenar una lista de elementos. Fue desarrollado en 1959 por Tony Hoare cuando era estudiante visitante en la Universidad Estatal de Moscú. El algoritmo es altamente utilizado en la industria por su rapidez (tiempo de ejecución promedio), estabilidad con grandes cantidades de datos y uso moderado de memoria.

Funciona mediante la selección de un “pivote” de la lista, la partición de la lista en dos sublistas de elementos menores y mayores que el pivote, y luego la recursión de estos pasos en cada sublista hasta que todos los elementos estén ordenados.

Veamos un ejemplo detallado de cómo ordenar la lista [4, 2, 7, 11, 1, 3, 10, 0, 9, 8, 6, 5] :

1. Seleccionamos un pivote: por ejemplo, el primer elemento de la lista, el 4 (podría ser cualquiera otra posición, incluso aleatoria).
2. Partimos la lista en dos sublistas: una con los elementos menores que 4 y otra con los elementos mayores que 4. La lista se divide en [2, 1, 3, 0] y [7, 11, 10, 9, 8, 6, 5].
3. Ordenamos recursivamente cada sublista hasta que todos los elementos estén ordenados: a. Ordenamos la sublista[2, 1, 3, 0] siguiendo los mismos pasos. Seleccione el primer elemento, 2, como pivote. Particione la lista en [1, 0] y [3]. Ordenar recursivamente cada sublista hasta que todos los elementos estén ordenados. b. Ordenamos la sublista [7, 11, 10, 9, 8, 6, 5] siguiendo los mismos pasos. Seleccione el primer elemento, 7, como pivote. Dividimos la lista en [4, 6, 5] y [11, 10, 9, 8]. Continuamos ordenando recursivamente cada sublista hasta que todos los elementos estén ordenados.
4. Una vez que todas las sublistas estén ordenadas, se combinarán entre ellas para formar la lista completa ordenada: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].

Ahora vemos una implementación directamente en Python.

from typing import List, Tuple, Union
from functools import reduce

IntListOrTuple = Union[List[int], Tuple[int]]

def ordenar_usando_quicksort(lista: IntListOrTuple) -> IntListOrTuple:
    """
    Ordena una lista de números enteros usando el algoritmo de quicksort.

    Args:
        lista List[int] o Tuple[int]: Lista de números enteros.
    returns:
        List[int] o Tuple[int]: Lista de números enteros ordenada.
    """
    # Hay más de un elemento de la lista, por lo tanto se puede dividir
    if len(lista) > 1:
        # Seleccionamos un pivote como referencia para subdividir la lista
        pivote = lista[0]
        # Guardamos la lista de números menores al pivote
        def incluir_numero_si_es_menor(
            mi_lista: IntListOrTuple, numero: int
        ) -> IntListOrTuple:
            if numero < pivote:
                mi_lista.append(numero)
            return mi_lista

        lista_menores = reduce(incluir_numero_si_es_menor, lista, [])
        # Guardamos la lista de números mayores al pivote
        def incluir_numero_si_es_mayor(
            mi_lista: IntListOrTuple, numero: int
        ) -> IntListOrTuple:
            if numero > pivote:
                mi_lista.append(numero)
            return mi_lista

        lista_mayores = reduce(incluir_numero_si_es_mayor, lista, [])
        # Realizamos una recursión donde creamos una lista con: el menor elemento + pivote + mayor elemento
        return (
            ordenar_usando_quicksort(lista_menores)
            + [pivote]
            + ordenar_usando_quicksort(lista_mayores)
        )
    # No hay más lista que subdividir, se devuelve el único valor
    return [lista[0]] if len(lista) == 1 else []

# Creamos la lista
mis_numeros_a_ordenar = [4, 2, 7, 11, 1, 3, 10, 0, 9, 8, 6, 5]
# La ordenamos
print(ordenar_usando_quicksort(mis_numeros_a_ordenar))
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

En resumen, es un algoritmo de ordenamiento eficiente, fácil de implementar y confiable que se puede utilizar para ordenar grandes conjuntos de datos. Con una complejidad temporal de O(n log n) en el peor de los casos, es una opción rápida y confiable para ordenar grandes conjuntos de datos.

Si estás buscando una solución de ordenamiento eficiente para tus proyectos, definitivamente debes considerar Quicksort.