Algoritmos de ordenación: burbuja, selección, inserción, merge sort y quicksort

Abrir el simulador

Burbuja, selección, inserción, merge sort y quicksort animados, con contador de comparaciones.

Ordenar una lista es uno de los problemas más estudiados de la informática. Hay decenas de algoritmos, y la diferencia entre uno sencillo y uno eficiente es enorme: con un millón de elementos, uno puede tardar horas y otro, menos de un segundo. Ver cada comparación e intercambio ayuda a entender por qué.

Lo que vas a aprender

La idea de cada algoritmo y cómo se programa.
Contar comparaciones e intercambios.
La complejidad en el mejor, el peor y el caso medio.
Qué significa que un algoritmo sea estable o “in situ”.
Qué algoritmo elegir según los datos.

Cómo se usa el simulador

Elige el algoritmo: burbuja, selección, inserción, merge sort o quicksort.
Datos: número de elementos (5 – 250) y su disposición inicial: aleatorio, casi ordenado o invertido. 🎲 Nuevos datos genera otros.
Avanza con ⏮, ▶ Ordenar y ⏭, o arrastra el deslizador de pasos. Ajusta la velocidad.
Los colores indican qué se compara, qué se intercambia, la clave y lo que ya está ordenado. Los contadores dan las comparaciones y los intercambios.
Cómo funciona resume la idea y la complejidad de cada algoritmo.

Fundamentos teóricos

Burbuja

Recorre la lista comparando vecinos y los intercambia si están al revés. En cada pasada, el mayor “sube” hasta el final.

for (i = 0; i < n - 1; i++)
    for (j = 0; j < n - 1 - i; j++)
        if (v[j] > v[j + 1]) intercambia(&v[j], &v[j + 1]);

Selección

Busca el mínimo de la parte sin ordenar y lo pone al principio. Hace siempre

n(n-1)/2

comparaciones, pero solo

n - 1

intercambios.

Inserción

Toma cada elemento y lo inserta en su sitio dentro de la parte ya ordenada, desplazando los mayores. Como al ordenar las cartas de una mano. Con datos casi ordenados es muy rápido.

Merge sort (mezcla)

Divide la lista en dos mitades, las ordena recursivamente y las mezcla en una sola ordenada. La mezcla de dos listas ordenadas es lineal.

T(n) = 2\,T(n/2) + n \quad\Rightarrow\quad O(n\log n)

Quicksort (rápido)

Elige un pivote, coloca a su izquierda los menores y a su derecha los mayores (partición) y ordena recursivamente cada lado. Si el pivote parte la lista por la mitad,

O(n\log n)

; si siempre elige el mínimo o el máximo (por ejemplo, con datos ya ordenados y el primer elemento como pivote), degenera a

O(n^2)

Comparativa

Algoritmo	Mejor	Medio	Peor	Memoria extra	Estable
Burbuja	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Sí
Selección	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	No
Inserción	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Sí
Merge sort	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	Sí
Quicksort	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	No

Un algoritmo es estable si mantiene el orden relativo de los elementos iguales. Importa al ordenar por varios criterios (por ejemplo, por nota y luego por apellido).

Ejemplos resueltos

Ejemplo 1 · Comparaciones de la burbuja

Con 5 elementos en el peor caso:

4 + 3 + 2 + 1 = 10

, es decir,

n(n - 1)/2

Ejemplo 2 · n² frente a n log n

Con 1000 elementos: un algoritmo cuadrático hace unas

1000^2/2 = 500\,000

comparaciones; merge sort, unas

1000 \cdot \log_2 1000 \approx 10\,000

. Cincuenta veces menos. Con un millón de elementos, la diferencia es de 25 000 veces.

Ejemplo 3 · Inserción con datos casi ordenados

Si cada elemento está como mucho a una posición de su sitio, inserción hace menos de

2n

comparaciones: prácticamente lineal.

Experimenta con el simulador

Casi ordenado

Con datos casi ordenados, compara inserción y selección. ¿Cuál hace menos comparaciones?

El peor caso de quicksort

Con datos invertidos, mira cómo trabaja quicksort. ¿Se acerca a

n^2

Muchos datos

Sube a 250 elementos y compara los contadores de burbuja y merge sort.

Errores frecuentes

Pensar que el algoritmo más rápido siempre es el mismo. Depende del tamaño y de cómo estén los datos.
Olvidar el caso peor de quicksort.
Confundir intercambios con comparaciones al medir el coste.

Herramientas relacionadas

Mejor y peor caso

Medir el coste experimentalmente.

Divide y vencerás

La idea de merge sort y quicksort.

Recursión

Funciones que se llaman a sí mismas.

Matemáticas

Física

Química

Electrónica

Programación

Inglés

Infantil

Algoritmos de ordenación: burbuja, selección, inserción, merge sort y quicksort

Abrir el simulador

Lo que vas a aprender

Cómo se usa el simulador

Fundamentos teóricos

Burbuja

Selección

Inserción

Merge sort (mezcla)

Quicksort (rápido)

Comparativa

Ejemplos resueltos

Experimenta con el simulador

Errores frecuentes

Herramientas relacionadas

Mejor y peor caso

Divide y vencerás

Recursión

Abrir el simulador

​Lo que vas a aprender

​Cómo se usa el simulador

​Fundamentos teóricos

​Burbuja

​Selección

​Inserción

​Merge sort (mezcla)

​Quicksort (rápido)

​Comparativa

​Ejemplos resueltos

​Experimenta con el simulador

​Errores frecuentes

​Herramientas relacionadas

Mejor y peor caso

Divide y vencerás

Recursión

Lo que vas a aprender

Cómo se usa el simulador

Fundamentos teóricos

Burbuja

Selección

Inserción

Merge sort (mezcla)

Quicksort (rápido)

Comparativa

Ejemplos resueltos

Experimenta con el simulador

Errores frecuentes

Herramientas relacionadas