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)

ordenamiento de un elemento de una lista

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

ordenamiento de la lista completa

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

Solución
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)
        

Retornar