Poner una lista en orden
Ordenar es colocar los elementos de una lista de menor a mayor. Un móvil lo hace con tus canciones, y una tienda con sus precios.
Hay muchas formas de hacerlo. Hoy aprendes tres algoritmos de ordenación y ves por qué unos trabajan más que otros.
Al final de esta lección
Nota
Puedo ordenar una lista con la ordenación de burbuja, por inserción y por mezcla.
Palabras clave
| Palabra | Qué significa |
|---|---|
| Ordenar | colocar los elementos de menor a mayor |
| Intercambio | cambiar de sitio dos elementos |
| Vuelta | una pasada completa por la lista |
| Mezcla | juntar dos listas ordenadas en una sola |
| Mediana | el valor del medio de una lista ordenada |
| Algoritmo de ordenación | una receta que deja una lista ordenada |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Ordena los ocho primeros días
docker exec jupyter python3 -c "import csv; h=[int(r['hires']) for r in csv.DictReader(open('hires.csv'))]; print(h[:8], sorted(h[:8]))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Python ya sabe ordenar, pero ¿cómo lo hace?
El Run imprime los ocho primeros alquileres, [137, 212, 173, 327, 204, 101, 243, 221], y después la misma lista ya ordenada, [101, 137, 173, 204, 212, 221, 243, 327].
La función sorted esconde el método. Para entenderlo, escribirás tú los tuyos.
La ordenación de burbuja compara vecinos
Recorres la lista y comparas cada elemento con el siguiente. Si están al revés, los intercambias.
Al final de una vuelta, el elemento más grande ha subido hasta el final, como una burbuja. Repites las vueltas hasta que la lista está en orden.
Ejemplo resuelto: burbuja con [5, 2, 4, 1]
| Vuelta | Lista al acabar | Intercambios |
|---|---|---|
| 1 | [2, 4, 1, 5] | 3 |
| 2 | [2, 1, 4, 5] | 1 |
| 3 | [1, 2, 4, 5] | 1 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
La burbuja en Python
def bubble_sort(items):
items = list(items)
for turn in range(len(items) - 1):
swaps = 0
for at in range(len(items) - 1 - turn):
if items[at] > items[at + 1]:
temp = items[at]
items[at] = items[at + 1]
items[at + 1] = temp
swaps = swaps + 1
print("vuelta", turn + 1, items, "cambios:", swaps)
return items
bubble_sort([5, 2, 4, 1])
La inserción coloca cada elemento en su sitio
Es como ordenar las cartas de tu mano. Coges la siguiente carta y la metes en su sitio entre las que ya tienes ordenadas.
La parte de la izquierda siempre está ordenada. Cada elemento nuevo se desliza hacia atrás hasta encontrar su hueco.
La inserción en Python
def insertion_sort(items):
items = list(items)
for start in range(1, len(items)):
value = items[start]
at = start - 1
while at >= 0 and items[at] > value:
items[at + 1] = items[at]
at = at - 1
items[at + 1] = value
print("insertado", value, items)
return items
insertion_sort([5, 2, 4, 1])
Un error frecuente
Advertencia
Mucha gente cree que burbuja e inserción son el mismo método porque los dos hacen cambios pequeños. La burbuja compara siempre vecinos y mueve lo grande hacia el final. La inserción toma un elemento y lo coloca entre los ya ordenados.
La mezcla junta dos listas ordenadas
Si tienes dos listas ya ordenadas, juntarlas es fácil. Miras el primer elemento de cada una y te llevas el menor.
Cuando una lista se acaba, copias lo que queda de la otra, que ya está ordenado. No hace falta compararlo.
Junta dos listas ordenadas
docker exec jupyter python3 -c "import heapq; print(list(heapq.merge([2, 5, 9], [3, 4, 10])))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
De listas de uno a una lista ordenada
El Run imprime [2, 3, 4, 5, 9, 10]. El módulo heapq ya trae una mezcla hecha, y la tuya hará lo mismo.
La ordenación por mezcla empieza con listas de un solo elemento, que siempre están ordenadas. Las junta de dos en dos, y repite con listas del doble de largo hasta que queda una.
Ejemplo resuelto: mezcla con [5, 2, 4, 1]
| Ronda | Listas que hay | Qué se junta |
|---|---|---|
| 0 | [5] [2] [4] [1] | Cuatro listas de uno |
| 1 | [2, 5] [1, 4] | [5] con [2] y [4] con [1] |
| 2 | [1, 2, 4, 5] | [2, 5] con [1, 4] |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
La mezcla de dos listas
def merge(left, right):
result = []
a = 0
b = 0
while a < len(left) and b < len(right):
if left[a] <= right[b]:
result.append(left[a])
a = a + 1
else:
result.append(right[b])
b = b + 1
# Lo que queda de una de las dos ya está ordenado: se copia.
return result + left[a:] + right[b:]
print(merge([2, 5, 9], [3, 4, 10]))
Para ir más lejos: la mediana
En el cuaderno, ordena todos los alquileres del año y mira el elemento del medio, el del índice 182. Esa es la mediana.
Prueba también con sorted(h)[-5:]: los cinco días con más alquileres. Ordenar convierte preguntas difíciles en preguntas de mirar una posición.