Estos son tres ordenamientos por comparación simple O(n²). Son lentos en entradas grandes pero fáciles de entender y útiles para enseñar la mecánica de ordenamiento.
Estos son tres ordenamientos por comparación simple O(n²). Son lentos en entradas grandes pero fáciles de entender y útiles para enseñar la mecánica de ordenamiento.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # element to place
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift bigger elements right
j -= 1
arr[j + 1] = key # drop key into the gap
return arr
insertion_sort([5, 2, 4, 1]) # -> [1, 2, 4, 5]
| Ordenamiento | Mejor | Peor | Estable | In-place |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Sí | Sí |
| Selection | O(n²) | O(n²) | No | Sí |
| Insertion | O(n) | O(n²) | Sí | Sí |
Insertion sort es genuinamente rápido para arrays pequeños o casi ordenados y se usa dentro de ordenamientos híbridos. Evite los tres en datos grandes desordenados — use ordenamientos O(n log n) en su lugar.
Estos ordenamientos construyen intuición para invariantes, intercambios y estabilidad antes de que aborde algoritmos avanzados.
Insertion sort en particular aparece dentro de ordenamientos de producción (como Timsort) para subarreglos pequeños.
Saber por qué son O(n²) hace que el salto a ordenamientos O(n log n) sea significativo.