Ordenamiento sencillo: bubble, selection e insertion sort
Ordenar: el problema estrella
Seguimos la serie de Algoritmos. En la entrega anterior vimos que la búsqueda binaria es maravillosa, pero exige una cosa: datos ordenados. Así que toca aprender a ordenar.
Ordenar es, posiblemente, el problema más estudiado de la informática, y hay decenas de algoritmos para hacerlo. Empezamos por los tres sencillos: bubble, selection e insertion sort. Te aviso ya: son lentos, los tres O(n²), y nadie los usa en serio para muchos datos. Entonces, ¿por qué empezar por ellos? Porque se entienden a la primera, te enseñan qué significa de verdad ordenar y ponen los cimientos para los métodos rápidos que veremos en la próxima entrega.
Bubble sort: las burbujas que suben
El bubble sort (ordenamiento de burbuja) es el más famoso y el más intuitivo. La idea: recorres la lista comparando cada par de elementos vecinos, y si están en el orden equivocado, los intercambias. Repites pasadas hasta que no haya ningún intercambio, señal de que ya está ordenado.
Se llama “burbuja” porque, en cada pasada, el elemento más grande “flota” hacia el final, como una burbuja subiendo.
FUNCION bubble_sort(lista)
n = longitud(lista)
REPETIR
huboCambio = falso
PARA i DESDE 0 HASTA n - 2
SI lista[i] > lista[i + 1] ENTONCES
intercambiar(lista[i], lista[i + 1])
huboCambio = verdadero
FIN SI
FIN PARA
MIENTRAS huboCambio
FIN FUNCION
Cada pasada deja un elemento más colocado en su sitio al final. Como hay n elementos y cada pasada recorre la lista, en el peor caso son n pasadas de n comparaciones: n por n, es decir, O(n²).
Selection sort: busca el mínimo y colócalo
El selection sort (por selección) trabaja distinto, pero igual de fácil de entender. Recorre la lista buscando el elemento más pequeño y lo pone el primero. Luego busca el más pequeño de lo que queda y lo pone segundo. Y así, seleccionando el mínimo de la parte sin ordenar y colocándolo.
FUNCION selection_sort(lista)
n = longitud(lista)
PARA i DESDE 0 HASTA n - 2
minimo = i
PARA j DESDE i + 1 HASTA n - 1
SI lista[j] < lista[minimo] ENTONCES
minimo = j
FIN SI
FIN PARA
intercambiar(lista[i], lista[minimo])
FIN PARA
FIN FUNCION
Fíjate en los dos bucles anidados: por cada posición, recorre el resto buscando el mínimo. Bucle dentro de bucle sobre los mismos datos: la alarma del O(n²) que ya conoces. Su única gracia frente al bubble es que hace muchos menos intercambios (uno por posición), lo cual a veces importa si mover datos es caro.
Insertion sort: como ordenar cartas en la mano
El insertion sort (por inserción) es mi favorito de los tres, y seguro que lo has hecho sin saberlo: es exactamente cómo ordenas las cartas en la mano. Coges una carta, y la insertas en su sitio entre las que ya tienes ordenadas, desplazando las que hagan falta. Carta a carta, tu mano siempre está ordenada.
FUNCION insertion_sort(lista)
PARA i DESDE 1 HASTA longitud(lista) - 1
actual = lista[i]
j = i - 1
MIENTRAS j >= 0 Y lista[j] > actual
lista[j + 1] = lista[j] // desplazo a la derecha
j = j - 1
FIN MIENTRAS
lista[j + 1] = actual // inserto en su hueco
FIN PARA
FIN FUNCION
En el peor caso (lista al revés) también es O(n²). Pero tiene un truco que lo hace especial, y lo cuento ahora.
El patito feo que a veces gana
Aquí está lo interesante: el insertion sort brilla cuando la lista está casi ordenada. Si los datos ya vienen casi en orden, el bucle interno apenas se mueve, y el algoritmo se acerca a O(n), lineal. En ese caso concreto, le da una paliza a los otros dos.
Esto no es una curiosidad de pizarra. En el mundo real, muchísimas veces los datos llegan casi ordenados (añades unos pocos elementos a algo ya ordenado), y por eso el insertion sort se usa de verdad dentro de algoritmos más grandes: los métodos rápidos que veremos suelen cambiar a insertion sort para los trozos pequeños, porque ahí es más eficiente. El patito feo tiene su momento.
Dos conceptos que vas a oír siempre: estabilidad e in-place
Al hablar de ordenación aparecen dos propiedades que conviene tener claras desde ya:
- In-place (en el sitio): un algoritmo ordena in-place si no necesita memoria extra apreciable, reordena la propia lista. Los tres de hoy son in-place: trabajan sobre la misma lista, sin copiarla. Eso es bueno para la complejidad espacial (la otra cara de la Big-O).
- Estabilidad: un algoritmo es estable si mantiene el orden relativo de los elementos iguales. Si ordenas una lista de personas por edad y dos tienen la misma, un algoritmo estable las deja en el mismo orden en que estaban. Bubble e insertion son estables; el selection, tal cual, no. Importa cuando ordenas por varios criterios encadenados.
No te agobies con esto ahora, pero te van a perseguir toda la serie, así que mejor saber qué significan.
Entonces, ¿para qué sirven si son lentos?
Buena pregunta. Para muchos datos, no los uses. Pero tienen su sitio:
- Para aprender. Entender estos tres es entender qué es ordenar. Los rápidos se construyen sobre estas ideas.
- Para pocos datos. Con diez o veinte elementos, un insertion sort es tan rápido como cualquier cosa y mucho más simple. La sofisticación no compensa.
- Para datos casi ordenados. Ya lo dije: ahí el insertion sort vuela.
Una nota sobre el número de intercambios
Un detalle que marca diferencias en la práctica: el selection sort hace pocos intercambios (uno por posición, n en total) aunque haga muchas comparaciones. El bubble, en cambio, puede hacer muchísimos intercambios. ¿Y eso importa? Cuando mover un dato es caro (objetos grandes, escrituras en disco), minimizar intercambios pesa más que minimizar comparaciones. Es otro recordatorio de que la Big-O no lo es todo: a veces, qué operación concreta cuesta más en tu caso decide el ganador, aunque la complejidad teórica sea la misma.
El libro para esta entrega
Para ver estos algoritmos animados, paso a paso y con humor, Comprender los algoritmos, de Aditya Bhargava dedica un capítulo precioso al selection sort que te deja la idea clavada. Es el compañero ideal de esta parte de la serie.
Lo siguiente: ordenar de verdad
Ya sabes ordenar, aunque sea despacio. La pregunta obvia es: ¿se puede hacer mejor que O(n²)? La respuesta es un sí rotundo.
En la próxima entrega entran los pesos pesados: merge sort y quick sort, los algoritmos O(n log n) que de verdad usan los lenguajes por dentro cuando llamas a una función de ordenación. Ahí verás la diferencia entre ordenar mil elementos en un millón de operaciones o en diez mil.
Preguntas frecuentes
¿Por qué los tres algoritmos sencillos son O(n²)?
Porque todos comparan, en esencia, cada elemento con muchos otros usando dos bucles anidados sobre los datos. Bubble compara vecinos en pasadas repetidas, selection busca el mínimo recorriendo el resto en cada posición, e insertion desplaza elementos hacia atrás. En el peor caso, el trabajo crece proporcional a n por n, es decir, O(n²): al doblar los datos, el trabajo se cuadruplica.
¿Cuándo es mejor el insertion sort?
Cuando la lista está casi ordenada o tiene pocos elementos. Si los datos ya vienen casi en orden, su bucle interno apenas trabaja y se acerca a O(n), batiendo a los otros dos. Por eso se usa de verdad dentro de algoritmos más grandes para ordenar los trozos pequeños, donde resulta más eficiente que métodos más sofisticados.
¿Qué significa que un algoritmo de ordenación sea estable?
Que mantiene el orden relativo de los elementos que son iguales entre sí. Si ordenas personas por edad y dos tienen la misma, un algoritmo estable las deja en el mismo orden en que estaban antes. Importa cuando ordenas por varios criterios seguidos. Bubble e insertion sort son estables; el selection sort, en su versión básica, no lo es.
Este artículo contiene enlaces de afiliado.
Compártelo si te ha resultado útil.
¿Te habías dado cuenta de que ordenas las cartas con un insertion sort? Cuéntame.
Y… en la próxima entrega, a ordenar rápido.
Artículos relacionados
Búsqueda lineal vs binaria: el poder de partir por la mitad
Buscar algo en una colección es el problema más cotidiano de la programación, y hay dos formas de hacerlo que no se parecen en nada. La búsqueda lineal mira uno a uno, de principio a fin: simple, funciona siempre, pero lenta. La búsqueda binaria parte la colección por la mitad una y otra vez y encuentra lo que buscas en un puñado de pasos, aunque haya millones de elementos. En esta segunda entrega de la serie de Algoritmos te explico las dos, su complejidad (O(n) frente a O(log n)), el requisito imprescindible de la binaria, sus versiones iterativa y recursiva, y cuándo usar cada una. Verás en acción esa diferencia brutal entre mirar un millón de cosas o solo veinte.
Qué es un algoritmo y la notación Big-O explicada paso a paso
Arranca la serie de Algoritmos, y lo hace por donde hay que empezar: aprendiendo a medir. Antes de comparar dos formas de resolver un problema necesitas saber cuál es mejor, y para eso está la notación Big-O. En esta primera entrega te explico qué es un algoritmo de verdad, qué es la complejidad temporal y espacial, y cómo leer esa notación que da tanto respeto: O(1), O(log n), O(n), O(n log n), O(n²) y la temida O(2^n). Lo verás con ejemplos cotidianos, sin matemáticas asustaviejas, y entenderás de una vez por qué un algoritmo puede tardar una décima de segundo y otro, con los mismos datos, dejarte el ordenador colgado una hora. Esto es la regla con la que se mide todo lo que viene después.
Algoritmos desde cero: del bubble sort a A*, toda la serie
Si la serie de Fundamentos te enseñó a escribir programas que funcionan, esta te va a enseñar a escribir programas que funcionan bien: rápidos, eficientes y capaces de aguantar montañas de datos sin ahogarse. Arranco la serie de Algoritmos, dieciséis entregas, los lunes, miércoles y viernes, para recorrer los algoritmos y estructuras de datos más famosos y útiles que existen, los que resuelven los problemas de verdad: buscar, ordenar, recorrer grafos, optimizar y trabajar con texto. Empezamos por la notación Big-O (medir si un programa escala o se ahoga) y terminamos en A*, el algoritmo que usan los videojuegos para encontrar caminos. Es lenguaje-agnóstico, con pseudocódigo y ejemplos. Este post es el índice y el calendario completo.