Bubble sort e insertion sort
Programe ambos algoritmos de ordenación cuadráticos, comprenda por qué son O(n²) y reconozca el caso en que insertion sort supera a merge sort.
Bubble sort e insertion sort es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Por qué estudiar algoritmos de ordenación O(n²)?
La ordenación de burbuja y la ordenación por inserción son O(n²) en el peor caso, por lo que resultan poco prácticas para entradas grandes. Aun así, en toda entrevista técnica seria se espera que sepa implementarlas y analizarlas. Enseñan conceptos fundamentales —comparación, intercambio, ordenación estable y comportamiento en el mejor caso— que se aplican a algoritmos más avanzados. Los entrevistadores las utilizan para comprobar si puede razonar sobre invariantes de bucle y notación asintótica desde los principios básicos.
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')Ordenación de burbuja: haga subir el máximo
La ordenación de burbuja recorre repetidamente el arreglo e intercambia los elementos adyacentes que están desordenados. Después de cada pasada completa, el elemento no ordenado más grande «sube» hasta su posición final al final del arreglo. Tras n-1 pasadas, todo el arreglo está ordenado. Su nombre proviene de la forma en que los elementos más grandes suben, como las burbujas. Es el algoritmo de ordenación más sencillo de describir, pero rara vez se utiliza en la práctica.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]Ordenación de burbuja con salida anticipada
Una ordenación de burbuja optimizada utiliza un indicador swapped: si una pasada interna completa no produce ningún intercambio, el arreglo ya está ordenado y terminamos antes. Esto proporciona un mejor caso de O(n) para una entrada ya ordenada, la única ventaja real de la ordenación de burbuja. Sin este indicador, siempre realiza O(n²) comparaciones. La optimización de salida anticipada es lo que los entrevistadores esperan cuando preguntan por mejoras de la ordenación de burbuja.
def bubble_sort_optimised(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 passAnálisis de complejidad de la ordenación de burbuja
El bucle externo de la ordenación de burbuja se ejecuta n-1 veces. El bucle interno se ejecuta n-1-i veces en cada pasada: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 comparaciones. Esto produce un caso medio y peor caso de O(n²). Con el indicador de salida anticipada, el mejor caso se reduce a O(n) para una entrada ordenada. La complejidad espacial es O(1): solo el intercambio requiere una variable temporal. La ordenación de burbuja es estable: los elementos iguales conservan su orden relativo, ya que solo intercambiamos elementos estrictamente mayores.
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5Ordenación por inserción: construir una mano ordenada
La ordenación por inserción imita la ordenación de una mano de cartas: tome la siguiente carta (elemento) e insértela en la posición correcta entre las cartas ya ordenadas de la izquierda. El invariante es que arr[0:i] siempre está ordenado. Para cada elemento nuevo, desplace los elementos mayores hacia la derecha para dejar espacio. Este algoritmo estable y que funciona in situ tiene un peor caso de O(n²), pero un mejor caso de O(n) con datos casi ordenados.
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]Ordenación por inserción paso a paso
Trace la ordenación por inserción sobre [3, 1, 4, 2]: i=1, key=1, desplace 3 hacia la derecha → [1, 3, 4, 2]. i=2, key=4, no hay desplazamientos → sin cambios. i=3, key=2, desplace primero 4 y luego 3 hacia la derecha → [1, 2, 3, 4]. Cada elemento se compara con los que están a su izquierda hasta encontrar su posición correcta. El bucle interno while realiza los desplazamientos mediante asignaciones, que son más rápidas que los intercambios porque cada desplazamiento requiere una asignación, frente a las tres de un intercambio.
def insertion_sort_trace(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]Ordenación por inserción con datos casi ordenados
La característica decisiva de la ordenación por inserción es su complejidad O(n + inversiones). Una inversión es un par (i,j) en el que i < j pero arr[i] > arr[j]. En arreglos casi ordenados con pocas inversiones, la ordenación por inserción es extremadamente rápida; en ocasiones, en la práctica, es más rápida que merge sort gracias a su simplicidad y a su patrón de acceso favorable para la caché. El Timsort de Python utiliza la ordenación por inserción en subarreglos pequeños precisamente por este motivo.
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)Estabilidad en la ordenación
Un algoritmo de ordenación es estable si los elementos iguales conservan su orden relativo original después de ordenar. Tanto la ordenación de burbuja como la ordenación por inserción son estables: nunca intercambian elementos iguales. La estabilidad es importante cuando ordena según varias claves de forma secuencial: ordene primero por la clave secundaria, de forma estable, y después por la clave principal, también de forma estable, para conservar el orden de la clave secundaria entre los empates. Merge sort también es estable; heap sort y quick sort generalmente no lo son.
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stableOrdenación por inserción mediante búsqueda binaria
El bucle interno de la ordenación por inserción encuentra la posición correcta y desplaza los elementos. Puede usar una búsqueda binaria para encontrar la posición con O(log i) comparaciones, pero los desplazamientos siguen requiriendo O(i) de tiempo, por lo que la complejidad general continúa siendo O(n²). La optimización reduce las comparaciones, lo que resulta útil con funciones de comparación costosas, pero no reduce el número total de operaciones. Esta «ordenación por inserción binaria» aparece en Timsort para tamaños de fragmento pequeños.
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]Burbuja frente a inserción: cuándo usar cada una
En las entrevistas, exponga esta comparación con seguridad: la ordenación por inserción es estrictamente mejor que la ordenación de burbuja; ambas tienen un peor caso de O(n²) y usan O(1) de espacio, pero la ordenación por inserción realiza menos escrituras (O(n+k) para k inversiones, frente a O(n²) en la ordenación de burbuja), aprovecha mejor la caché y es la opción práctica para valores pequeños de n (Timsort la utiliza). La única ventaja real de la ordenación de burbuja es su sencillez pedagógica. En producción, utilice siempre la ordenación integrada del lenguaje.
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]Contar inversiones como métrica
El número de inversiones de un arreglo es igual al número de pares (i,j) en los que i < j pero arr[i] > arr[j]. La ordenación por inserción realiza exactamente tantos desplazamientos como inversiones haya, una observación útil. Para contar inversiones eficientemente, en O(n log n), se necesita una variante de merge sort. A veces, como seguimiento de las conversaciones sobre ordenación, los entrevistadores preguntan: «¿Hasta qué punto tiene en cuenta las inversiones su algoritmo?»
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs invertedComprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió que: la ordenación de burbuja realiza n-1 pasadas y en cada una lleva el máximo actual hasta su posición final, con un peor caso de O(n²), pero un mejor caso de O(n) gracias al indicador de salida anticipada, la ordenación por inserción desplaza los elementos hacia la derecha para insertar la clave actual en la posición ordenada correcta y se ejecuta en O(n + inversiones), por lo que es óptima para datos casi ordenados y ambos algoritmos son estables, usan O(1) de espacio y tienen un peor caso de O(n²), pero la ordenación por inserción es claramente preferible a la ordenación de burbuja en todas las situaciones prácticas. A continuación, implementaremos merge sort desde cero.
Preguntas frecuentes
¿La lección «Bubble sort e insertion sort» es gratis?
Sí — el texto completo de «Bubble sort e insertion sort» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Bubble sort e insertion sort»?
Programe ambos algoritmos de ordenación cuadráticos, comprenda por qué son O(n²) y reconozca el caso en que insertion sort supera a merge sort. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Bubble sort e insertion sort»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Bubble sort e insertion sort
- Merge sort: dividir, ordenar y combinar
- Quick sort y selección del pivote
- Ordenaciones sin comparación y sort() de Python