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.
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 -= 1Se 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.
