Ordenamiento por inserción y por selección

Código en:JavaC#PythonJavaScript

En resumen: El ordenamiento por inserción coloca cada elemento en su lugar de la parte ordenada y es rápido con entradas casi ordenadas, mientras que el ordenamiento por selección elige el menor y siempre hace unas n²/2 comparaciones.

Problema

La página de productos lenta

La tienda ordena los pedidos del día por hora de entrega, y la página de administración muestra todos los productos por precio. En los dos sitios hay el mismo código antiguo:

def selection_sort(times):
    for i in range(len(times) - 1):
        best = i
        for j in range(i + 1, len(times)):
            if times[j] < times[best]:
                best = j
        if best != i:
            times[i], times[best] = times[best], times[i]

today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"]
selection_sort(today)
print(" ".join(today))

Salida

08:45 09:15 10:30 11:00 14:30 16:45

Con seis pedidos es instantáneo. Pero hay 50 000 productos, y la página tarda segundos en abrirse. El código encuentra el elemento menor en todo el resto, lo pone delante y repite. Con 50 000 elementos son 49 999 + 49 998 + … + 1 = 1 249 975 000 comparaciones. Cada vez, incluso cuando los productos ya están ordenados y solo se han intercambiado dos.

Esta lección tiene los dos algoritmos básicos de ordenamiento: este, el ordenamiento por selección, y el ordenamiento por inserción. Los contarás comparación a comparación y verás dónde encaja cada uno.

La idea

Ordenamiento por inserción: como las cartas en la mano

Así ordenas las cartas en la mano. Tomas la siguiente carta y la deslizas a la izquierda, pasando las mayores, hasta que llega a una menor. Las cartas a su izquierda siempre están ordenadas.

def insertion_sort(times):
    for i in range(1, len(times)):
        key = times[i]
        j = i - 1
        while j >= 0 and times[j] > key:
            times[j + 1] = times[j]
            j -= 1
        times[j + 1] = key

key es el pedido que se va a colocar. j empieza en el pedido a su izquierda. Mientras el pedido en j sea posterior a key, se mueve un lugar a la derecha y j baja. Donde el bucle se detiene hay un hueco en j + 1, y key va ahí.

En Python times[j] > key compara los strings carácter por carácter. Las horas tienen un cero inicial (09:15), así que el orden del texto es el orden de la hora.

today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"]
insertion_sort(today)
print(" ".join(today))

Salida

08:45 09:15 10:30 11:00 14:30 16:45

Míralo

Las cartas en su lugar

def insertion_sort(times):
    for i in range(1, len(times)):
        key = times[i]
        j = i - 1
        while j >= 0 and times[j] > key:
            times[j + 1] = times[j]
            j -= 1
        times[j + 1] = key

Paso a paso, en palabras

1. 6 pedidos por hora de entrega. A la izquierda crece la parte ordenada: al principio es solo el primer pedido, 14:30.
2. key = 09:15. 1 pedido posterior se mueve un lugar a la derecha, hasta el mismo principio, y 09:15 entra en el lugar 0. 1 comparación.
3. key = 11:00. 1 pedido posterior se mueve un lugar a la derecha, hasta 09:15, y 11:00 entra en el lugar 1. 2 comparaciones.
4. key = 16:45. 14:30 no es posterior: nada se mueve, y 16:45 entra en el lugar 3. 1 comparación.
5. key = 10:30. 3 pedidos posteriores se mueven un lugar a la derecha, hasta 09:15, y 10:30 entra en el lugar 1. 4 comparaciones.
6. key = 08:45. 5 pedidos posteriores se mueven un lugar a la derecha, hasta el mismo principio, y 08:45 entra en el lugar 0. 5 comparaciones.
7. Ordenado: 13 comparaciones y 10 desplazamientos. La lista casi ordenada del día necesita solo 6 comparaciones y 1 desplazamiento.

Cada carta hace tanto trabajo como cartas posteriores tiene delante en la parte ordenada. 16:45 va después de todas y no mueve nada. 08:45 es anterior a todas y mueve las cinco.

Pruébalo

Cuenta

El mismo ordenamiento por inserción, pero se cuenta cada comparación y cada desplazamiento. Primero con los pedidos de la escena, luego con una lista casi ordenada: un pedido llegó un poco después del siguiente.

def insertion_sort(times):
    comparisons = 0
    shifts = 0
    for i in range(1, len(times)):
        key = times[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if times[j] <= key:
                break
            times[j + 1] = times[j]
            shifts += 1
            j -= 1
        times[j + 1] = key
    print(f"Comparaciones: {comparisons}, desplazamientos: {shifts}")

today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"]
insertion_sort(today)
print(" ".join(today))

almost = ["08:45", "09:15", "11:00", "10:30", "14:30", "16:45"]
insertion_sort(almost)

Salida

Comparaciones: 13, desplazamientos: 10
08:45 09:15 10:30 11:00 14:30 16:45
Comparaciones: 6, desplazamientos: 1

La diferencia viene de cuándo se detiene el bucle interior. Si el pedido ya va después de todo lo que tiene a su izquierda, basta una comparación. Así que:

• el mejor caso es una lista ordenada: n - 1 comparaciones, cero desplazamientos. O(n);
• el peor caso es una lista invertida: cada pedido viaja hasta el lugar 0, n(n - 1)/2 comparaciones y otros tantos desplazamientos. O(n²);
• con una entrada aleatoria cada pedido recorre en promedio la mitad de la parte ordenada: unas n²/4. Sigue siendo O(n²).

La lista casi ordenada está cerca del mejor caso: cada pedido mal colocado añade una comparación o dos.

Pruébalo

Predice la salida

Los pedidos ya están ordenados. ¿Qué imprime el ordenamiento por inserción con contadores?

today = ["08:45", "09:15", "10:30", "11:00", "14:30", "16:45"]
insertion_sort(today)

Respuesta

Comparaciones: 15, desplazamientos: 0

Comparaciones: 0, desplazamientos: 0

Comparaciones: 5, desplazamientos: 0

Comprobar

La idea

Ordenamiento por selección: elige el más temprano

El código antiguo del principio hace otra cosa. Para el lugar i mira todo el resto, encuentra el pedido más temprano (su índice es best: el mejor hasta ahora) y lo intercambia con el pedido en i. Después ya no se toca el lugar i.

def selection_sort(times):
    for i in range(len(times) - 1):
        best = i
        for j in range(i + 1, len(times)):
            if times[j] < times[best]:
                best = j
        if best != i:
            times[i], times[best] = times[best], times[i]

Paso a paso, en palabras

1. Los mismos 6 pedidos. El ordenamiento por selección revisa todo lo que aún no está ordenado, encuentra el pedido más temprano y lo pone delante.
2. i = 0: 5 comparaciones en el resto. La más temprana es 08:45, y intercambia su lugar con 14:30.
3. i = 1: 4 comparaciones en el resto. La más temprana es 09:15, y ya está en su lugar: sin intercambio.
4. i = 2: 3 comparaciones en el resto. La más temprana es 10:30, y intercambia su lugar con 11:00.
5. i = 3: 2 comparaciones en el resto. La más temprana es 11:00, y intercambia su lugar con 16:45.
6. i = 4: 1 comparación en el resto. La más temprana es 14:30, y intercambia su lugar con 16:45.
7. 15 comparaciones y 4 intercambios. Las comparaciones siempre son n(n − 1)/2 = 15: la lista casi ordenada también necesita 15, con 1 intercambio.

def selection_sort(times):
    comparisons = 0
    swaps = 0
    for i in range(len(times) - 1):
        best = i
        for j in range(i + 1, len(times)):
            comparisons += 1
            if times[j] < times[best]:
                best = j
        if best != i:
            times[i], times[best] = times[best], times[i]
            swaps += 1
    print(f"Comparaciones: {comparisons}, intercambios: {swaps}")

today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"]
selection_sort(today)
print(" ".join(today))

almost = ["08:45", "09:15", "11:00", "10:30", "14:30", "16:45"]
selection_sort(almost)

Salida

Comparaciones: 15, intercambios: 4
08:45 09:15 10:30 11:00 14:30 16:45
Comparaciones: 15, intercambios: 1

Las dos listas necesitan 15 comparaciones: para estar seguro de que encontró el más temprano, el ordenamiento por selección mira todo el resto cada vez. Con n pedidos son (n - 1) + (n - 2) + … + 1 = n(n - 1)/2 comparaciones con cualquier entrada. No hay un caso mejor.

Su fuerza está en otro sitio: hay como máximo n - 1 intercambios, uno por lugar. El de inserción desplaza hasta n²/2 veces. Cuando comparar es barato y mover es caro (registros grandes que se copian, o escrituras en memoria flash que se desgasta), los pocos intercambios importan.

Míralo

Mídelo

La operación es una comparación de dos elementos. El ordenamiento por inserción se ejecuta con tres entradas: aleatoria, casi ordenada (ordenada, y luego n/20 pares vecinos intercambiados) e invertida. El de selección se ejecuta solo con entrada aleatoria, porque hace lo mismo con cualquier entrada.

• Ordenamiento por inserción, entrada aleatoria O(n²)
• Ordenamiento por inserción, entrada casi ordenada O(n)
• Ordenamiento por inserción, entrada invertida O(n²)
• Ordenamiento por selección, entrada aleatoria O(n²)

Algoritmo	n = 10	n = 100	n = 1000	n = 10.000	n = 100.000
Ordenamiento por inserción, entrada aleatoria	37	2481	254.808	25.057.917	≈ 2.505.791.700
Ordenamiento por inserción, entrada casi ordenada	9	104	1049	10.474	104.755
Ordenamiento por inserción, entrada invertida	45	4950	499.500	49.995.000	≈ 4.999.500.000
Ordenamiento por selección, entrada aleatoria	45	4950	499.500	49.995.000	≈ 4.999.500.000

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

def insertion_sort(times):
    for i in range(1, len(times)):
        key = times[i]
        j = i - 1
        while j >= 0 and times[j] > key:
            times[j + 1] = times[j]
            j -= 1
        times[j + 1] = key

Con 1000 elementos: entrada aleatoria 254 808, casi ordenada 1049, invertida 499 500, y selección 499 500 con cualquier entrada. Con 100 000 solo se ejecuta la casi ordenada: las otras harían miles de millones de comparaciones. La página con 50 000 productos está entre las dos: más de mil millones de comparaciones con el ordenamiento por selección.

Pruébalo

Encuentra el error

Esta versión deja un pedido fuera de su lugar:

today = ["14:30", "09:15", "11:00", "16:45", "10:30", "08:45"]
insertion_sort(today)
print(" ".join(today))

Salida

14:30 08:45 09:15 10:30 11:00 16:45

Elige la línea con el error.

1def insertion_sort(times):2 for i in range(1, len(times)):3 key = times[i]4 j = i - 15 while j > 0 and times[j] > key:6 times[j + 1] = times[j]7 j -= 18 times[j + 1] = key

Comprobar

Pruébalo

Pon las líneas en orden

Este es el cuerpo del bucle exterior del ordenamiento por inserción. Ponlo en orden.

1. key = times[i]↑↓
2. while j >= 0 and times[j] > key:↑↓
3. times[j + 1] = key↑↓
4. j -= 1↑↓
5. j = i - 1↑↓
6. times[j + 1] = times[j]↑↓

Comprobar

La idea

Dónde se usan

Son lentos con muchos elementos, pero no son solo para aprender. El ordenamiento por inserción es el más rápido para arreglos pequeños y para los casi ordenados: sin recursión, sin memoria extra, y su bucle interior es corto.

Por eso las funciones de ordenamiento incorporadas lo usan por dentro:

Más precisamente, para curiosos

• Java. Arrays.sort para objetos y Collections.sort son TimSort: busca en los datos tramos ya ordenados y alarga los cortos con ordenamiento por inserción binaria, hasta unos 32 elementos. Arrays.sort para números es quicksort de doble pivote, que ordena las partes pequeñas con ordenamiento por inserción.
• C#. Array.Sort y List<T>.Sort son introsort: un quicksort que cambia al ordenamiento por inserción para partes de hasta 16 elementos.
• Python. list.sort() y sorted() son TimSort (desde 3.11 con la regla de mezcla de powersort), y también alargan los tramos cortos con ordenamiento por inserción binaria.
• JavaScript. En V8 (Chrome, Node.js) Array.prototype.sort es TimSort desde 2018, con el mismo ordenamiento por inserción binaria para tramos cortos.

El ordenamiento por inserción binaria encuentra el lugar de key con búsqueda binaria, no uno por uno. Las comparaciones pasan a ser unas n log n, pero los desplazamientos siguen igual.

Los arreglos grandes necesitan algoritmos O(n log n). El primero es el ordenamiento por mezcla.

Ejercicio

Los pedidos más grandes arriba

Resuélvelo en tu propio editor.

Por total, el mayor primero. El informe diario muestra los pedidos por total, del mayor al menor. Escribe sort_by_total_descending(totals) con ordenamiento por inserción y ordena pedidos de 46 €, 13 €, 89 €, 23 € y 67 €. La salida es:

Salida

89 €
67 €
46 €
23 €
13 €

Más tareas

• Ordenamiento por selección desde atrás. Escribe un ordenamiento por selección que cada vez encuentre el pedido más tardío y lo ponga al final de la parte sin ordenar. Cuenta las comparaciones: ¿siguen siendo n(n - 1)/2?
• Desplazamientos contra intercambios. Ejecuta las versiones con contadores en una lista invertida de 10 pedidos. ¿Cuántos desplazamientos hace el ordenamiento por inserción y cuántos intercambios hace el de selección?
• Ordenamiento por inserción binaria. Encuentra el lugar de key en la parte ordenada con búsqueda binaria, y luego desplaza. ¿Cuántas comparaciones hace con 1000 pedidos aleatorios?

Test

Ponte a prueba

1. La lista de pedidos ya está ordenada por hora, solo dos vecinos están intercambiados. ¿Qué algoritmo termina antes?

Ordenamiento por inserción: casi cada pedido se compara una vez y se quedaIgual de rápidos: los dos son O(n²)Ordenamiento por selección: hace el menor número de intercambios

2. ¿Cuántas comparaciones hace el ordenamiento por selección con 1000 pedidos?

Unas 1000 si están ordenados499 500, con cualquier entradaUnas 10 000

3. ¿Cuándo es mejor el ordenamiento por selección?

Cuando cada escritura en un lugar es cara: hace como máximo n - 1 intercambiosCuando la lista está casi ordenadaCuando hay un millón de elementos

4. ¿Qué hace el ordenamiento por inserción con un pedido anterior a todo lo de la parte ordenada?

Lo intercambia con el primeroDesplaza todos un lugar a la derecha y lo pone en el lugar 0Lo deja al final

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Parámetros y return · Complejidad en tiempo: contar pasos · Big-O: cómo crece el trabajo · Mejor caso, caso promedio y peor caso
• Continúa en: Ordenamiento por mezcla y «divide y vencerás» · Quicksort y el mal pivote · Ordenamiento estable y el ordenamiento incorporado · Divide y vencerás y el árbol de recursión
• Ejercicios sobre el tema: Ordenamiento