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.

Relacionado:  Moda de arreglo en Java (elemento más repetido)

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.


Estoy disponible para trabajar en tu proyecto o realizar tu tarea pendiente, no dudes en ponerte en contacto conmigo.
Si el post fue de tu agrado muestra tu apoyo compartiéndolo, suscribiéndote al blog, siguiéndome o realizando una donación.

Suscribir por correo

Ingresa tu correo y recibirás mis últimas entradas sobre programación, open source, bases de datos y todo lo relacionado con informática

Únete a otros 707 suscriptores


parzibyte

Programador freelancer listo para trabajar contigo. Aplicaciones web, móviles y de escritorio. PHP, Java, Go, Python, JavaScript, Kotlin y más :) https://parzibyte.me/blog/software-creado-por-parzibyte/

0 Comments

Deja un comentario

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

A %d blogueros les gusta esto: