23. Algoritmo Quicksort

Implementa el algoritmo de ordenamiento Quicksort.

Crea una función que reciba una lista de elementos (números o cadenas) y la ordene utilizando el principio de Quicksort. La función debe devolver una nueva lista ordenada.

def quicksort(lista: list) -> list:
    # Tu código aquí
    pass

quicksort([3, 6, 8, 10, 1, 2, 1])
# [1, 1, 2, 3, 6, 8, 10]

quicksort(["z", "a", "c", "b"])
# ["a", "b", "c", "z"]

quicksort([])
# []

quicksort([5])
# [5]

Ratoncito

Implementa la versión básica de Quicksort, eligiendo un pivote simple (por ejemplo, el primer o último elemento).

Dragón

Implementa una versión más robusta de Quicksort:

• Elige un pivote de forma más inteligente (por ejemplo, la mediana de tres).

• Optimiza para listas pequeñas (por ejemplo, cambiando a Insertion Sort cuando la sublista es muy pequeña).

• Considera la estabilidad del algoritmo o explora cómo manejar elementos duplicados.