Un método de ordenamiento simplemente es un algoritmo que permite colocar lo elementos de un arreglo, tabla o lista, en orden secuencial, es decir, de mayor a menor o viceversa. El ordenamiento de los datos puede darse de manera iterativa o recursiva. En esta ocasión, aprenderemos a realizar los métodos de ordenamiento clásicos en el lenguaje Python de manera iterativa ¿Listos para comenzar? ¡Manos a la obra!
Tabla de Contenido
Ordenamiento por burbuja (Bubble Sort)
Es el método más básico, consiste en ir comparando un elemento con su vecino siguiente, el elemento cambia de lugar con su vecino si es mayor que el susodicho, en caso contrario se queda en su lugar. Este proceso se repetirá indefinidamente mientras haya elementos fuera de lugar.
Comencemos por crear nuestro método, el cual recibirá como parámetro la lista de elementos sin ordenar.
def burbuja(lista):
Ponemos una bandera para asegurar la mínima ejecución del método, es decir, que por lo menos se pueda realizar una vez.
bandera = True
Mientras bandera sea True…
while bandera:
Cambiamos la bandera a False, de esta manera cuando no queden elementos por ordenar se acabará el ciclo while.
bandera = False
Hacemos un ciclo for desde 0 hasta el total de elementos de la lista – 1. Nos conviene contar desde 0 ya que si son 6 elementos, se detendrá en 5 (6 – 1) y seguirán siendo 6 repeticiones.
for i in range(len(lista) - 1):
Si el elemento en la posición i es mayor a su vecino (i + 1)…
if lista[i] > lista[i + 1]:
Entonces los intercambiamos, es decir lo que estaba en la posición i, pasa a la posición i + 1 y viceversa.
lista[i], lista[i + 1] = lista[i + 1], lista[i]
Como se logró el intercambio, ponemos bandera a True para que no se salga y revise el siguiente elemento.
bandera = True
Entonces, el método queda como sigue:
def burbuja(lista):
bandera = True
while bandera:
bandera = False
for i in range(len(lista) - 1):
if lista[i] > lista[i + 1]:
lista[i], lista[i + 1] = lista[i + 1], lista[i]
bandera = True
Hagamos una prueba:
lista = [2, 6, 12, 4, 32, 1]
print ("Ordenamiento por burbuja")
print ("Antes de ordenar:" + str(lista))
burbuja(lista)
print ("Después de ordenar:" + str(lista))
El output debería ser el siguiente.
Ordenamiento por selección (Selection Sort)
Este método revisa una lista de elementos, selecciona el primer elemento como el mínimo posible y lo compara con el resto de la lista hasta encontrar el valor más bajo, cuando esto sucede se hace el intercambio y se procede a revisar el siguiente elemento bajo las mismas condiciones. Esto se repite hasta finalizar toda la lista.
Comencemos por crear nuestro método, el cual recibirá como parámetro la lista de elementos sin ordenar.
def seleccion(lista):
Recorremos toda la lista del primero al último
for i in range(len(lista)):
Establecemos el valor actual como el valor mínimo.
valorMinimo = i
Por cada elemento, revisamos a partir del siguiente (i + 1) hasta el último
for j in range(i + 1, len(lista)):
Si el elemento siguiente es inferior al mínimo
if lista[j] < lista[valorMinimo]:
Convertimos ese elemento en el mínimo.
valorMinimo = j
Al salir del segundo ciclo for, hacemos el intercambio de posiciones del elemento seleccionado con al valor mínimo.
lista[i], lista[valorMinimo] = lista[valorMinimo], lista[i]
Así entonces, el método queda como sigue:
def seleccion(lista):
for i in range(len(lista)):
valorMinimo = i
for j in range(i + 1, len(lista)):
if lista[j] < lista[valorMinimo]:
valorMinimo = j
lista[i], lista[valorMinimo] = lista[valorMinimo], lista[i]
Hagamos una prueba de esto:
print ("Ordenamiento por selección")
lista2 = [23, 6, 7, 1, 15, 10]
print ("Antes de ordenar:" + str(lista2))
seleccion(lista2)
print ("Después de ordenar:" + str(lista2))
El output es como sigue:
Ordenamiento por inserción (Insertion Sort)
Este algoritmo es similar al anterior. Partiendo del supuesto que el primer elemento es el menor, se recorre desde el siguiente y se intercambia solo si es mayor igual a cero o mayor al anterior. Esto se repite hasta finalizar toda la lista.
Comenzamos por crear el método, el cual recibe como parámetro, la lista en desorden.
def insercion(lista):
Hacemos el primer ciclo, el cual revisará desde el segundo elemento (posición 1) hasta el final de la lista.
for i in range(1, len(list)):
Guardamos el elemento actual como el elemento a insertar.
insertar = lista[i]
Recuperamos siempre el anterior.
anterior = i - 1
Con un segundo ciclo, intentamos mover adelante cualquier elemento anterior cuya posición sea mayor o igual a cero y aquellos elementos anteriores que sean mayores al elemento a insertar.
while anterior >= 0 and lista[anterior] > insertar:
Así que si se cumple. Se intercambia el elemento siguiente con el anterior
lista[anterior + 1] = lista[anterior]
Y descendemos posiciones en la lista de anteriores.
anterior -= 1
Finalizado el ciclo, insertamos el elemento en la posición siguiente.
lista[anterior + 1] = insertar
En resumen, así queda el método completo:
def insercion(lista):
for i in range(1, len(lista)):
insertar = lista[i]
anterior = i - 1
while anterior >= 0 and lista[anterior] > insertar:
lista[anterior + 1] = lista[anterior]
anterior -= 1
lista[anterior + 1] = insertar
Hagamos una prueba de esto:
print ("Ordenamiento por inserción")
lista3 = [73, 6, 7, 21, 1, 10]
print ("Antes de ordenar:" + str(lista3))
insercion(lista3)
print ("Después de ordenar:" + str(lista3))
El output resultante es:
Ordenación por combinación (Merge Sort)
Usando un poco de recursividad, este algoritmo toma una lista y la divide en dos partes, ordena ambas partes y luego las fusiona. Después repite este mismo proceso hasta que no queden ningún elemento sin ordenar. Para poder lograrlo, se crearan dos métodos: uno que ordene las dos partes y otro que haga la recursión.
Lo primero será crear el método para combinar ambas lista.
def combinar(izquierda, derecha):
Creamos la lista ordenada vacía
ordenada = []
La posición inicial de ambas listas es 0
pos_izq = pos_der = 0
Obtenemos la longitud de ambas listas.
len_izq, len_der = len(izquierda), len(derecha)
Con un ciclo for, recorremos la totalidad de ambas listas.
for i in range(len_izq + len_der):
Si ambas posiciones son menores a sus longitudes.
if pos_izq < len_izq and pos_der < len_der:
Si el elemento en la izquierda es menor o igual al de la derecha.
if izquierda[pos_izq]<=derecha[pos_der]:
Añadimos ese elemento a la lista ordenada.
ordenada.append(izquierda[pos_izq])
Aumentamos la posición de la izquierda.
pos_izq+=1
De lo contrario:
else:
Añadimos el elemento de la lista derecha a la lista ordenada.
ordenada.append(derecha[pos_der])
Movemos la posición derecha.
pos_der+=1
Si llegamos al final de la lista izquierda
elif pos_izq == len_izq:
Añadimos el elemento siguiente de la lista derecha.
ordenada.append(derecha[pos_der])
Y avanzamos a la siguiente posición de la derecha.
pos_der+=1
Pero si es la lista derecha la que llego a su fin.
elif pos_der == len_der:
Añadimos el elemento siguiente de la lista izquierda.
ordenada.append(izquierda[pos_izq])
Y avanzamos a la siguiente posición de la izquierda.
pos_izq+=1
Cuando ya no quede nada, regresamos la lista cordenada y combinada.
return ordenada
Entonces, el primer método queda así:
def combinar(izquierda, derecha):
ordenada = []
pos_izq = pos_der = 0
len_izq, len_der = len(izquierda), len(derecha)
for i in range(len_izq + len_der):
if pos_izq < len_izq and pos_der < len_der:
if izquierda[pos_izq]<=derecha[pos_der]:
ordenada.append(izquierda[pos_izq])
pos_izq+=1
else:
ordenada.append(derecha[pos_der])
pos_der+=1
elif pos_izq == len_izq:
ordenada.append(derecha[pos_der])
pos_der+=1
elif pos_der == len_der:
ordenada.append(izquierda[pos_izq])
pos_izq+=1
return ordenada
El segundo método tomará la lista y de manera recursiva, la dividirá en dos partes e invocará el método anterior con las dos listas para ordenarlas y combinarlas hasta que no quede ningún elemento sin ordenar.
Comenzamos definiendo el método que recibirá la lista a ordenar como parámetro.
def mergeSort(lista):
Si la lista tiene un único elemento.
if len(lista) == 1:
Entonces, el método se acaba y se regresa ese único elemento.
return lista
De lo contrario:
else:
Obtener la mitad de la lista
mitad = len(lista) // 2
Con esa mitad, generar la lista izquierda
izquierda = mergeSort(lista[:mitad])
Luego la lista derecha.
derecha = mergeSort(lista[mitad:])
Entonces, ordenamos ambas listas y las combinamos en una sola
combinada = combinar(izquierda, derecha)
Retornamos la lista resultante.
return combinada
El método completo es como sigue:
def mergeSort(lista):
if len(lista) == 1:
return lista
else:
mitad = len(lista) // 2
izquierda = mergeSort(lista[:mitad])
derecha = mergeSort(lista[mitad:])
combinada = combinar(izquierda, derecha)
return combinada
Igual que los anteriores, hagamos una prueba:
print ("Ordenamiento por combinación")
lista4 = [173, 6, 27, 21, 81, 10]
print ("Antes de ordenar:" + str(lista4))
lista4 = mergeSort(lista4)
print ("Después de ordenar:" + str(lista4))
El output resultante es el siguiente:
Ordenamiento básico con Python
Python tiene integrado un método para hacer ordenamiento, llamado sort, el cual hace comparaciones en busca siempre del menor. Este método tiene dos parámetros opcionales que son: key, el cual permite definir un valor clave y reverse que es un boolean para determinar si la lista se ordena mayor a menor (True) o no (False).
Por ejemplo, consideremos la siguiente lista:
lista5 = ["José", "Ricardo", "Marcos", "Sísifo", "Alberto", "Sabrina"]
Colocamos la lista en el output.
print ("Antes de ordenar:" + str(lista5))
Aplicamos el método sort.
lista5.sort()
Veamos como queda:
print ("Ordenado simple:" + str(lista5))
Ahora, ordenamos a la inversa.
lista5.sort(reverse=True)
Y lo mostramos en el output.
print ("Ordenado inverso:" + str(lista5))
El resultado es el siguiente:
También existe una función llamada sorted, la cual acepta cualquier elemento mientras este pueda ser iterable. Esto la hace perfecta para ordenar objetos más complejos.
Por ejemplo, consideremos la siguiente lista de personas:
personas = [
("Ricardo", 22),
("Sofía", 33),
("Armando", 19),
("Saúl", 20)
]
Las mostramos en el output antes de ordenar:
print ("Antes de ordenar:" + str(personas))
Ahora, las ponemos en orden y guardamos el resultado en otra lista.
orden1 = sorted(personas)
Así quedan ordenadas por nombre:
print ("Ordenar por nombre:" + str(orden1))
Ahora con itemgetter, las ordenamos por edad.
orden2 = sorted(personas, key=itemgetter(1))
Y mostramos el resultado en el output.
print ("Ordenar por edad:" + str(orden2))
No olvidemos hacer el import para itemgetter:
from operator import itemgetter
Entonces, el output queda como sigue:
¡Y ESO ES TODO POR AHORA!
¿Te ha resultado? Déjanos saber en los comentarios aquí abajo, en nuestra cuenta de twitter @cablenaranja7 o en nuestra página de facebook.
Docente, IT Manager, Blogger & Developer. Escribo por diversión, educo por pasión. | Grandstanding is not my thing.
