Quicksort en Python – Algoritmo de ordenamiento

Dejar un comentario / Algoritmos, python / Por

En este post de programación en Python te enseñaré a ordenar una lista o arreglo usando el ordenamiento rápido también conocido como Quicksort.

Quicksort en Python

Como en varios tutoriales de Python, me referiré a las listas ya sea con ese nombre o con “arreglo”.

Ordenamiento según pivote

La mayor parte de este algoritmo cae en la elección del pivote. Lo que se hace es tener dos puntos en los límites de la lista. El primero en el inicio, y el segundo en el final. Mientras la lista esté ordenada, vamos acercando estos puntos.

Con “acercar” los puntos me refiero a que la variable de la izquierda va en aumento, y la variable de la derecha en decremento.

Recuerda que solo se acercan mientras el arreglo esté ordenado, es decir, que todos los elementos de la izquierda sean menores al pivote y todos los de la derecha sean mayores a este.

Si el arreglo no está ordenado, justo aquí se intercambia la izquierda con la derecha (y acá sucede la magia del ordenamiento) asegurando que todos los elementos a la izquierda del pivote son menores que este, y los de la derecha, mayores.

Además de eso, la lista se va dividiendo y se indica al invocador de la función en cuál punto se quedó, para volver a ordenarla.

Todo esto se entiende mejor en el código.

Partición

Aquí vemos la función de la partición, que es la que tiene mayor parte del código. Se encarga de acercar los índices entre sí e ir ordenando. Se detiene cuando la lista o parte de la lista que le dieron ya está ordenada; y regresa el índice en donde se quedó.

def particion(arreglo, izquierda, derecha):
    pivote = arreglo[izquierda]
    while True:
        # Mientras cada elemento desde la izquierda esté en orden (sea menor que el
        # pivote) continúa avanzando el índice
        while arreglo[izquierda] < pivote:
            izquierda += 1

        # Mientras cada elemento desde la derecha esté en orden (sea mayor que el
        # pivote) continúa disminuyendo el índice
        while arreglo[derecha] > pivote:
            derecha -= 1

        """
            Si la izquierda es mayor o igual que la derecha significa que no
            necesitamos hacer ningún intercambio
            de variables, pues los elementos ya están en orden (al menos en esta
            iteración)
        """
        if izquierda >= derecha:
            # Indicar "en dónde nos quedamos" para poder dividir el arreglo de nuevo
            # y ordenar los demás elementos
            return derecha
        else:
            # Nota: yo sé que el else no hace falta por el return de arriba, pero así el algoritmo es más claro
            """
                Si las variables quedaron "lejos" (es decir, la izquierda no superó ni
                alcanzó a la derecha)
                significa que se detuvieron porque encontraron un valor que no estaba
                en orden, así que lo intercambiamos
            """
            arreglo[izquierda], arreglo[derecha] = arreglo[derecha], arreglo[izquierda]
            """
                Ya intercambiamos, pero seguimos avanzando los índices
            """
            izquierda += 1
            derecha -= 1

Se puede observar que hay un ciclo infinito (línea 3) que se detiene solo cuando la izquierda es mayor o igual que la derecha. También es importante notar que el intercambio se hace en la línea 32.

Quicksort

Veamos ahora la función quicksort que usa recursividad, pero para dividir el arreglo invoca a la función de partición vista previamente.

def quicksort(arreglo, izquierda, derecha):
    if izquierda < derecha:
        indiceParticion = particion(arreglo, izquierda, derecha)
        quicksort(arreglo, izquierda, indiceParticion)
        quicksort(arreglo, indiceParticion + 1, derecha)

Lo que se hace es dividir el arreglo a la mitad, y luego volver a dividirlo hasta que todo esté perfectamente ordenado.

Poniendo todo junto

A continuación dejo un ejemplo, además del código completo. Por cierto, en este caso estamos ordenando un arreglo de números pero bien podría ser una lista de cadenas o de cualquier tipo de dato (haciendo la comparación necesaria).

"""
==============================
https://parzibyte.me/blog
==============================
"""
def quicksort(arreglo, izquierda, derecha):
    if izquierda < derecha:
        indiceParticion = particion(arreglo, izquierda, derecha)
        quicksort(arreglo, izquierda, indiceParticion)
        quicksort(arreglo, indiceParticion + 1, derecha)


def particion(arreglo, izquierda, derecha):
    pivote = arreglo[izquierda]
    while True:
        # Mientras cada elemento desde la izquierda esté en orden (sea menor que el
        # pivote) continúa avanzando el índice
        while arreglo[izquierda] < pivote:
            izquierda += 1

        # Mientras cada elemento desde la derecha esté en orden (sea mayor que el
        # pivote) continúa disminuyendo el índice
        while arreglo[derecha] > pivote:
            derecha -= 1

        """
            Si la izquierda es mayor o igual que la derecha significa que no
            necesitamos hacer ningún intercambio
            de variables, pues los elementos ya están en orden (al menos en esta
            iteración)
        """
        if izquierda >= derecha:
            # Indicar "en dónde nos quedamos" para poder dividir el arreglo de nuevo
            # y ordenar los demás elementos
            return derecha
        else:
            # Nota: yo sé que el else no hace falta por el return de arriba, pero así el algoritmo es más claro
            """
                Si las variables quedaron "lejos" (es decir, la izquierda no superó ni
                alcanzó a la derecha)
                significa que se detuvieron porque encontraron un valor que no estaba
                en orden, así que lo intercambiamos
            """
            arreglo[izquierda], arreglo[derecha] = arreglo[derecha], arreglo[izquierda]
            """
                Ya intercambiamos, pero seguimos avanzando los índices
            """
            izquierda += 1
            derecha -= 1

"""
Modo de uso:
"""

arreglo = [5, 1, 2, 1, 1, 3, 5, 1, 5, 1, 99, 231, 234, 12, 121,
           312, 123, 123, 12, 312, 321, 312, 31, 23, 12, 3123, 123, ]
print("Antes de ordenarlo: ")
print(arreglo)
quicksort(arreglo, 0, len(arreglo) - 1)
print("Después de ordenarlo: ")
print(arreglo)

Te invito a explorar mi blog para ver más contenido sobre Python.

Estoy aquí para ayudarte 🤝💻

Estoy aquí para ayudarte en todo lo que necesites. Si requieres alguna modificación en lo presentado en este post, deseas asistencia con tu tarea, proyecto o precisas desarrollar un software a medida, no dudes en contactarme. Estoy comprometido a brindarte el apoyo necesario para que logres tus objetivos. Mi correo es parzibyte(arroba)gmail.com, estoy como@parzibyte en Telegram o en mi página de contacto

No te pierdas ninguno de mis posts 🚀🔔

Suscríbete a mi canal de Telegram para recibir una notificación cuando escriba un nuevo tutorial de programación.

Dejar un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *