Quicksort en Python – Algoritmo de ordenamiento

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ó.

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.

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).

Si quieres puedes ejecutar el código en este enlace. Te invito a explorar mi blog para ver más contenido sobre Python.

Encantado de ayudarte


Estoy disponible para trabajar en tu proyecto, modificar el programa del post o realizar tu tarea pendiente, no dudes en ponerte en contacto conmigo.

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