18 - Listas: ordenamiento de sus elementos
Otro algoritmo muy común que debe conocer y entender un programador es el ordenamiento de una lista de datos.
El ordenamiento de una lista se logra intercambiando las componentes de manera que:
lista[0] <= lista[1] <= lista[2] etc.
El contenido de la componente lista[0] sea menor o igual al contenido de la componente lista[1] y así sucesivamente.
Si se cumple lo dicho anteriormente decimos que la lista está ordenado de menor a mayor. Igualmente podemos ordenar una lista de mayor a menor.
Tengamos en cuenta que la estructura de datos lista en Python es mutable, eso significa que podemos modificar sus elementos por otros.
Se puede ordenar tanto listas con componentes de tipo int, float como cadena de caracteres. En este último caso el ordenamiento es alfabético.
Problema 1:
Se debe crear y cargar una lista donde almacenar 5 sueldos. Desplazar el valor mayor de la lista a la última posición.
La primera aproximación para llegar en el próximo problema al ordenamiento completo de una lista tiene por objetivo analizar los intercambios de elementos dentro de la lista y dejar el mayor en la última posición.
El algoritmo consiste en comparar si la primera componente es mayor a la segunda, en caso que la condición sea verdadera, intercambiamos los contenidos de las componentes.
Vamos a suponer que se ingresan los siguientes valores por teclado:
1200 750 820 550 490
En este ejemplo: ¿es 1200 mayor a 750? La respuesta es verdadera, por lo tanto intercambiamos el contenido de la componente 0 con el de la componente 1.
Luego comparamos el contenido de la componente 1 con el de la componente 2: ¿Es 1200 mayor a 820?
La respuesta es verdadera entonces intercambiamos.
Si hay 5 componentes hay que hacer 4 comparaciones, por eso el for se repite 4 veces.
Generalizando: si la lista tiene N componentes hay que hacer N-1 comparaciones.
Cuando x = 0 x = 1 x = 2 x = 3 750 750 750 750 1200 820 820 820 820 1200 550 550 550 550 1200 490 490 490 490 1200
Podemos ver cómo el valor más grande de la lista desciende a la última componente. Empleamos una variable auxiliar (aux) para el proceso de intercambio:
Programa: ejercicio88.py
sueldos=[]
for x in range(5):
valor=int(input("Ingrese sueldo:"))
sueldos.append(valor)
print("Lista sin ordenar")
print(sueldos)
for x in range(4):
if sueldos[x]>sueldos[x+1]:
aux=sueldos[x]
sueldos[x]=sueldos[x+1]
sueldos[x+1]=aux
print("Lista con el último elemento ordenado")
print(sueldos)
Al salir del for el contenido de la lista es la siguiente:
750 820 550 490 1200
Analizando el algoritmo podemos comprobar que el elemento mayor de la lista se ubica ahora en el último lugar.
Podemos volver a ejecutar el programa y veremos que siempre el elemento mayor queda al final.
Pero con un único for no se ordena una lista. Solamente está ordenado el último elemento de la lista.
Problema 2:
Se debe crear y cargar una lista donde almacenar 5 sueldos. Ordenar de menor a mayor la lista.
Ahora bien como vimos en el problema anterior con los 4 elementos que nos quedan podemos hacer el mismo proceso visto anteriormente, con lo cual quedará ordenado otro elemento de la lista. Este proceso lo repetiremos hasta que quede ordenado por completo la lista.
Como debemos repetir el mismo algoritmo podemos englobar todo el bloque en otra estructura repetitiva.
Realicemos una prueba del siguiente algoritmo:
Cuando k = 0 x = 0 x = 1 x = 2 x = 3 750 750 750 750 1200 820 820 820 820 1200 550 550 550 550 1200 490 490 490 490 1200 Cuando k = 1 x = 0 x = 1 x = 2 x = 3 750 750 750 750 820 550 550 550 550 820 490 490 490 490 820 820 1200 1200 1200 1200 Cuando k = 2 x = 0 x = 1 x = 2 x = 3 550 550 550 550 750 490 490 490 490 750 750 750 820 820 820 820 1200 1200 1200 1200 Cuando k = 3 x = 0 x = 1 x = 2 x = 3 490 490 490 490 550 550 550 550 750 750 750 750 820 820 820 820 1200 1200 1200 1200
Programa: ejercicio89.py
sueldos=[]
for x in range(5):
valor=int(input("Ingrese sueldo:"))
sueldos.append(valor)
print("Lista sin ordenar")
print(sueldos)
for k in range(4):
for x in range(4):
if sueldos[x]>sueldos[x+1]:
aux=sueldos[x]
sueldos[x]=sueldos[x+1]
sueldos[x+1]=aux
print("Lista ordenada")
print(sueldos)
¿Porque repetimos 4 veces el for externo?
Como sabemos cada vez que se repite en forma completa el for interno queda ordenada una componente de la lista. A primera vista diríamos que deberíamos repetir el for externo la cantidad de componentes de la lista, en este ejemplo la lista sueldos tiene 5 componentes.
Si observamos, cuando quedan dos elementos por ordenar, al ordenar uno de ellos queda el otro automáticamente ordenado (podemos imaginar que si tenemos una lista con 2 elementos no se requiere el for externo, porque este debería repetirse una única vez)
Una última consideración a este ALGORITMO de ordenamiento es que los elementos que se van ordenando continuamos comparándolos.
Ejemplo: En la primera ejecución del for interno el valor 1200 queda ubicado en la posición 4 de la lista. En la segunda ejecución comparamos si el 820 es mayor a 1200, lo cual seguramente será falso.
Podemos concluir que la primera vez debemos hacer para este ejemplo 4 comparaciones, en la segunda ejecución del for interno debemos hacer 3 comparaciones y en general debemos ir reduciendo en uno la cantidad de comparaciones.
Si bien el algoritmo planteado funciona, un algoritmo más eficiente, que se deriva del anterior es el plantear un for interno con la siguiente estructura:
for k in range(4):
for x in range(4-k):
if sueldos[x]>sueldos[x+1]:
aux=sueldos[x]
sueldos[x]=sueldos[x+1]
sueldos[x+1]=aux
Es decir restarle el valor del contador del for externo.
Problemas propuestos
- Crear una lista y almacenar los nombres de 5 países. Ordenar alfabéticamente la lista e imprimirla.
- Solicitar por teclado la cantidad de empleados que tiene la empresa. Crear y cargar una lista con todos los sueldos de dichos empleados. Imprimir la lista de sueldos ordenamos de menor a mayor.
- Cargar una lista con 5 elementos enteros. Ordenarla de menor a mayor y mostrarla por pantalla, luego ordenar de mayor a menor e imprimir nuevamente.
ejercicio90.py
paises=[]
for x in range(5):
nom=input("Ingrese el nombre de pais:")
paises.append(nom)
for k in range(4):
for x in range(4-k):
if paises[x]>paises[x+1]:
aux=paises[x]
paises[x]=paises[x+1]
paises[x+1]=aux
print("Listado de paises")
print(paises)
ejercico91.py
cantidad=int(input("Cuantos empleados tiene la empresa?"))
sueldos=[]
for x in range(cantidad):
su=int(input("Ingrese sueldo:"))
sueldos.append(su)
# ordenamos la lista
for k in range(cantidad-1):
for x in range(cantidad-1-k):
if sueldos[x]>sueldos[x+1]:
aux=sueldos[x]
sueldos[x]=sueldos[x+1]
sueldos[x+1]=aux
print("Lista de sueldos ordenados")
print(sueldos)
ejercicio92.py
lista=[]
for x in range(5):
valor=int(input("Ingrese valor:"))
lista.append(valor)
# ordenamos de menor a mayor
for k in range(4):
for x in range(4-k):
if lista[x]>lista[x+1]:
aux=lista[x]
lista[x]=lista[x+1]
lista[x+1]=aux
print("Lista ordenada de menor a mayor")
print(lista)
# ordenamos de mayor a menor
for k in range(4):
for x in range(4-k):
if lista[x]<lista[x+1]:
aux=lista[x]
lista[x]=lista[x+1]
lista[x+1]=aux
print("Lista ordenada de mayor a menor")
print(lista)