Data Structure & Algorithms
Comparación de bubble sort, selection sort e insertion sort mediante invariantes, estabilidad, casos de entrada y complejidad cuadrática.
Bubble sort, selection sort e insertion sort no suelen ser la mejor opción para ordenar grandes volúmenes. Su valor principal es educativo: hacen visibles comparaciones, intercambios, invariantes, estabilidad y análisis de casos.
También pueden ser útiles en segmentos pequeños o datos casi ordenados, especialmente insertion sort.
Un algoritmo recibe una secuencia y un comparador que define el orden.
type Comparator<T> = (a: T, b: T) => number;La salida debe cumplir dos propiedades:
Un array creciente que perdió duplicados no es un sorting correcto.
Compara pares adyacentes e intercambia los que están en orden incorrecto. En cada pasada, el mayor elemento pendiente “sube” hasta el final.
[5, 2, 4, 1]
[2, 5, 4, 1]
[2, 4, 5, 1]
[2, 4, 1, 5] ← 5 queda fijofunction bubbleSort<T>(values: T[], compare: Comparator<T>): void {
for (let end = values.length - 1; end > 0; end -= 1) {
let swapped = false;
for (let index = 0; index < end; index += 1) {
if (compare(values[index], values[index + 1]) > 0) {
[values[index], values[index + 1]] = [
values[index + 1],
values[index],
];
swapped = true;
}
}
if (!swapped) return;
}
}Después de una pasada con límite end, el sufijo posterior a end está ordenado y contiene los elementos más grandes en sus posiciones finales.
swapped: O(n), porque una pasada confirma que ya está ordenado;O(n²);O(1);> 0.Si intercambias también claves iguales, pierdes estabilidad sin mejorar el orden.
Busca el mínimo del segmento no ordenado y lo coloca en la siguiente posición.
ordenado | no ordenado
[] | [5, 2, 4, 1]
[1] | [2, 4, 5]
[1, 2] | [4, 5]function selectionSort<T>(values: T[], compare: Comparator<T>): void {
for (let start = 0; start < values.length - 1; start += 1) {
let bestIndex = start;
for (let index = start + 1; index < values.length; index += 1) {
if (compare(values[index], values[bestIndex]) < 0) {
bestIndex = index;
}
}
if (bestIndex !== start) {
[values[start], values[bestIndex]] = [values[bestIndex], values[start]];
}
}
}Antes de cada iteración de start, el prefijo values[0..start) contiene los elementos más pequeños en orden final.
Siempre hace aproximadamente n(n - 1) / 2 comparaciones:
O(n²);O(n);O(1);Puede ser útil cuando escribir o intercambiar es mucho más costoso que comparar, porque hace pocos swaps.
2A, 2B, 1Al mover 1 al inicio mediante swap, puede quedar:
1, 2B, 2ALas claves 2 cambiaron su orden relativo.
Una variante estable puede desplazar elementos en lugar de intercambiar, pero cambia la cantidad de escrituras.
Mantiene un prefijo ordenado e inserta cada nuevo elemento en su posición.
[5] | 2, 4, 1
[2, 5] | 4, 1
[2, 4, 5] | 1
[1, 2, 4, 5]function insertionSort<T>(values: T[], compare: Comparator<T>): void {
for (let index = 1; index < values.length; index += 1) {
const current = values[index];
let position = index - 1;
while (position >= 0 && compare(values[position], current) > 0) {
values[position + 1] = values[position];
position -= 1;
}
values[position + 1] = current;
}
}En lugar de hacer un swap por paso, guarda current y desplaza el bloque. Esto reduce escrituras innecesarias.
Antes de procesar index, el prefijo values[0..index) está ordenado y contiene los mismos elementos que ese prefijo original.
O(n);O(n²);O(1);current.Una inversión es una pareja (i, j) con i < j pero values[i] > values[j].
Insertion sort mueve cada elemento una posición por cada inversión que debe corregir. Su tiempo puede expresarse como O(n + I), donde I es la cantidad de inversiones.
Por eso funciona bien en datos casi ordenados.
Binary search puede encontrar la posición de inserción en O(log n) comparaciones, pero desplazar los elementos sigue costando O(n). El tiempo asintótico total continúa siendo O(n²).
Puede ayudar si comparar es muy costoso y mover referencias es barato.
| Algoritmo | Mejor | Promedio/peor | Estable | Fortaleza |
|---|---|---|---|---|
| Bubble sort | O(n) optimizado | O(n²) | Sí | Invariante visual sencillo |
| Selection sort | O(n²) | O(n²) | No habitual | Pocos intercambios |
| Insertion sort | O(n) | O(n²) | Sí | Datos pequeños o casi ordenados |
Aunque su peor caso es cuadrático, insertion sort tiene:
Un sort avanzado puede dividir la entrada y usar insertion sort cuando cada segmento queda por debajo de un umbral.
Estos algoritmos muestran tres formas frecuentes de construir una solución:
Para demostrar un loop:
Las implementaciones modifican el array original. Para una API no mutante:
function sortedCopy<T>(values: readonly T[], compare: Comparator<T>): T[] {
const copy = [...values];
insertionSort(copy, compare);
return copy;
}La copia usa O(n) de memoria, aunque el algoritmo interno sea in-place.
NaN o es inconsistente.index < end incorrectos en bubble sort.current durante los desplazamientos de insertion sort.O(n log n).¿Por qué insertion sort puede ser O(n) en un array ya ordenado?
Porque para cada elemento la primera comparación confirma que ya está después de un valor menor o igual. No realiza desplazamientos, así que hace una cantidad lineal de trabajo.