Ordenar una lista de precios
Un algoritmo de ordenación coloca los elementos de una lista de menor a mayor. Tres clásicos son la ordenación por inserción, por selección y por mezcla, y su coste es muy distinto.
Una tienda online ordena 10.000 productos por precio. Con un método lento son unos 50 millones de comparaciones. Con uno rápido, unas 130.000.
Al final de esta lección
Nota
Puedo seguir paso a paso la ordenación por inserción, por selección y por mezcla.
Palabras clave
| Palabra | Qué significa |
|---|---|
| Ordenar | colocar los elementos de menor a mayor |
| Comparación | mirar cuál de dos elementos es menor |
| Inserción | colocar un elemento en su sitio entre los ya ordenados |
| Selección | elegir el menor y ponerlo al principio |
| Mezcla | juntar dos listas ordenadas en una |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
La inserción coloca cada elemento en su sitio
Imagina que ordenas cartas en la mano. Coges la siguiente y la metes donde le toca entre las que ya tienes ordenadas.
La ordenación por inserción hace lo mismo con una lista. Si la lista ya está ordenada, cada elemento se compara una sola vez. Si está al revés, se compara con todos los anteriores.
Ordenación por inserción con su cuenta
# Ordenación por inserción: cada elemento se coloca entre los ya ordenados.
items = [40, 7, 25, 3, 18]
steps = 0
for i in range(1, len(items)):
current = items[i]
j = i - 1
while j >= 0:
steps = steps + 1
if items[j] > current:
items[j + 1] = items[j]
j = j - 1
else:
break
items[j + 1] = current
print(items)
print("Comparaciones:", steps)
# Prueba con [3, 7, 18, 25, 40], que ya está ordenada.
La selección busca siempre el menor
La ordenación por selección busca el menor de toda la lista y lo pone en la primera posición. Después busca el menor del resto y lo pone en la segunda.
Para encontrar el menor mira todos los que quedan, aunque la lista ya esté ordenada. Por eso hace siempre el mismo número de comparaciones.
Ordenación por selección con su cuenta
# Ordenación por selección: busca el menor y ponlo delante.
items = [40, 7, 25, 3, 18]
steps = 0
for i in range(len(items)):
smallest = i
for j in range(i + 1, len(items)):
steps = steps + 1
if items[j] < items[smallest]:
smallest = j
items[i], items[smallest] = items[smallest], items[i]
print(items)
print("Comparaciones:", steps)
# Prueba con [3, 7, 18, 25, 40], que ya está ordenada.
La orden sort ordena líneas
printf "40\n7\n25\n3\n18\n" | sort -n | tr "\n" " "Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que un algoritmo cuadrático nunca vale la pena. Con pocos datos, o con datos casi ordenados, la inserción es sencilla y rápida. Lo que importa es cómo crece el coste cuando n es grande.
La mezcla junta dos listas ordenadas
Para mezclar dos listas ordenadas, mira el primer elemento de cada una y toma el menor. Repite hasta vaciar una. El resto de la otra ya está ordenado.
La ordenación por mezcla parte la lista por la mitad, ordena cada mitad y las mezcla. Parte tantas veces como puedas, unas log2 de n, y en cada nivel mezcla n elementos.
Mezclar dos listas ordenadas
# Mezcla: junta dos listas ya ordenadas en una.
def merge_two(left, right):
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i = i + 1
else:
result.append(right[j])
j = j + 1
result = result + left[i:] + right[j:]
return result
print(merge_two([3, 25, 40], [7, 18]))
# Cambia las listas, pero mantenlas ordenadas.
Comparaciones aproximadas con 1.000 elementos
| Algoritmo | Crecimiento | Comparaciones |
|---|---|---|
| Inserción, peor caso | Cuadrático | Unas 500.000 |
| Selección, siempre | Cuadrático | 499.500 |
| Mezcla | n por log de n | Unas 10.000 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Comparaciones de la selección con 1.000 elementos
python3 -c "n = 1000; print(n * (n - 1) // 2)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Pasos de la mezcla con 1.000 elementos
python3 -c "import math; print(round(1000 * math.log2(1000)))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.