3.06 · Ordenamiento: Burbuja, Selección, Inserción

🧠 Teoría y conceptos — 🫧 1. Ordenamiento Burbuja (Bubble Sort)

Idea: comparar pares adyacentes e intercambiarlos si están en orden incorrecto. Repetir hasta que no haya intercambios.

Traza visual con [4, 1, 5, 2, 3]

Figura: Burbuja - paso 1: comparar 4 y 1

Figura: Burbuja - paso 2: 1 ya en su lugar

Figura: Burbuja - paso 3: comparar 5 y 2

Figura: Burbuja - paso 4: estado tras pasada 1

Pasada 1:

• [4, 1, 5, 2, 3] → comparo 4,1 → swap → [1, 4, 5, 2, 3]
• [1, 4, 5, 2, 3] → comparo 4,5 → ok
• [1, 4, 5, 2, 3] → comparo 5,2 → swap → [1, 4, 2, 5, 3]
• [1, 4, 2, 5, 3] → comparo 5,3 → swap → [1, 4, 2, 3, 5]

El 5 ya está en su lugar (es el mayor, "burbujeó" al final).

Figura: Burbuja - estado tras pasada 1

Pasada 2 (solo hasta el 4):

• [1, 4, 2, 3, 5] → 1,4 ok
• [1, 4, 2, 3, 5] → 4,2 → swap → [1, 2, 4, 3, 5]
• [1, 2, 4, 3, 5] → 4,3 → swap → [1, 2, 3, 4, 5]

Pasada 3 (solo hasta el 3):

• [1, 2, 3, 4, 5] → todo en orden. Terminamos.

Implementación

void burbuja(int arr[], int n) {

for (int i = 0; i < n - 1; i++) {       // n-1 pasadas

bool huboIntercambio = false;

for (int j = 0; j < n - 1 - i; j++) {  // hasta donde ya está ordenado
if (arr[j] > arr[j + 1]) {

// swap

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

huboIntercambio = true;

}

}

if (!huboIntercambio) break;  // ya está ordenado, salimos

}

}

Análisis

• Comparaciones en el peor caso: n × (n-1) / 2 → O(n²)
• Intercambios en el peor caso: n × (n-1) / 2 → O(n²)
• Mejor caso (ya ordenado): O(n) — solo una pasada sin intercambios.

¿Cuándo usarlo?

• Arreglos pequeños (n < 50).
• Como herramienta pedagógica (es fácil de entender).
• Nunca en producción. Usa std::sort.

🎯 2. Ordenamiento por Selección (Selection Sort)

Idea: buscar el mínimo de todo el arreglo, colocarlo al inicio. Repetir con el resto.

Figura: Selección - paso 1: buscar el mínimo

Figura: Selección - paso 2: siguiente mínimo

Traza con `[4, 1, 5, 2, 3]`:

Pasada 1: mínimo de [4, 1, 5, 2, 3] = 1 (posición 1). Intercambio con posición 0: [1, 4, 5, 2, 3] Pasada 2: mínimo de [4, 5, 2, 3] = 2 (posición 3). Intercambio con posición 1: [1, 2, 5, 4, 3] Pasada 3: mínimo de [5, 4, 3] = 3 (posición 4). Intercambio con posición 2: [1, 2, 3, 4, 5] Pasada 4: mínimo de [4, 5] = 4 (posición 3). Intercambio con posición 3: [1, 2, 3, 4, 5] (sin cambio real)

Implementación

void seleccion(int arr[], int n) {

for (int i = 0; i < n - 1; i++) {

int posMin = i;

for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[posMin]) {

posMin = j;

}

}

// swap arr[i] y arr[posMin]

if (posMin != i) {  // solo si encontramos uno menor

int temp = arr[i];

arr[i] = arr[posMin];

arr[posMin] = temp;

}

}

}

Análisis

• Comparaciones: siempre (n-1) × n / 2 → O(n²)
• Intercambios: a lo sumo n-1 → O(n) (¡mejor que burbuja en swaps!)

¿Cuándo usarlo?

• Cuando el costo de comparar es bajo pero el de intercambiar es alto (escritura en memoria flash, por ejemplo).

📥 3. Ordenamiento por Inserción (Insertion Sort)

Idea: tomar cada elemento y "insertarlo" en su lugar correcto dentro de la parte ya ordenada.

Figura: Inserción - paso 1: insertar siguiente elemento

Traza con `[4, 1, 5, 2, 3]`:

i=0: [4] (trivial, ya ordenado) i=1: tomo 1, lo inserto en [4]. Comparo: 1 < 4 → muevo 4 a la derecha, pongo 1 al inicio: [1, 4] i=2: tomo 5, lo inserto en [1, 4]. 5 > 4 → queda al final: [1, 4, 5] i=3: tomo 2, lo inserto en [1, 4, 5]. 2 < 4 → muevo 4, 2 > 1 → pongo 2 entre 1 y 4: [1, 2, 4, 5] i=4: tomo 3, lo inserto en [1, 2, 4, 5]. 3 < 4 → muevo 4. 3 > 2 → pongo 3 entre 2 y 4: [1, 2, 3, 4, 5]

Implementación

void insercion(int arr[], int n) {

for (int i = 1; i < n; i++) {

int actual = arr[i]; // elemento a insertar

int j = i - 1;

// mover elementos mayores a la derecha

while (j >= 0 && arr[j] > actual) {

arr[j + 1] = arr[j];

j--;

}

arr[j + 1] = actual; // insertar en su lugar

}

}

Análisis

• Comparaciones en el peor caso: O(n²)
• Mejor caso (ya ordenado): O(n) — solo una pasada.
• Promedio: O(n²), pero con una constante menor que burbuja.

¿Cuándo usarlo?

• Arreglos casi ordenados (rendimiento excelente).
• Arreglos pequeños.
• En combinación con algoritmos avanzados (Timsort lo usa como subrutina).

🚀 5. La opción profesional: std::sort

En C++ real, nunca implementas estos algoritmos. Usa la librería estándar:

#include <algorithm>
int arr[] = {5, 2, 8, 1, 9, 3};

int n = 6;

sort(arr, arr + n); // ordena de menor a mayor

// Para mayor a menor:

sort(arr, arr + n, greater<int>());

Complejidad: O(n log n) — mucho más rápido.

Versión Java:

import java.util.Arrays;
int[] arr = {5, 2, 8, 1, 9, 3};

Arrays.sort(arr);

Versión Python:

arr = [5, 2, 8, 1, 9, 3]

arr.sort() # o sorted(arr) retorna una nueva lista

Regla: entiende los 3 algoritmos, pero usa `sort()` en tu código real. La diferencia entre saber cómo funciona y reinventarlo es productividad.

🧪 6. Medición empírica

#include <iostream>
#include <chrono>
#include <cstdlib>
using namespace std;
int main() {

const int N = 10000;

int* datos = new int[N];
for (int i = 0; i < N; i++) datos[i] = rand() % 100000;
int* copia = new int[N];

// Burbuja

memcpy(copia, datos, N * sizeof(int));

auto t1 = chrono::high_resolution_clock::now();

burbuja(copia, N);

auto t2 = chrono::high_resolution_clock::now();

cout << "Burbuja: "

<< chrono::duration_cast<chrono::milliseconds>(t2 - t1).count()

<< " ms" << endl;

// Selección

memcpy(copia, datos, N * sizeof(int));

auto t3 = chrono::high_resolution_clock::now();

seleccion(copia, N);

auto t4 = chrono::high_resolution_clock::now();

cout << "Seleccion: "

<< chrono::duration_cast<chrono::milliseconds>(t4 - t3).count()

<< " ms" << endl;

// Inserción

memcpy(copia, datos, N * sizeof(int));

auto t5 = chrono::high_resolution_clock::now();

insercion(copia, N);

auto t6 = chrono::high_resolution_clock::now();

cout << "Insercion: "

<< chrono::duration_cast<chrono::milliseconds>(t6 - t5).count()

<< " ms" << endl;

// sort

memcpy(copia, datos, N * sizeof(int));

auto t7 = chrono::high_resolution_clock::now();

sort(copia, copia + N);

auto t8 = chrono::high_resolution_clock::now();

cout << "std::sort: "

<< chrono::duration_cast<chrono::microseconds>(t8 - t7).count()

<< " us" << endl; // microsegundos, no milisegundos

delete[] datos;

delete[] copia;

return 0;

}

Salida típica (n=10 000):

Burbuja: 180 ms

Seleccion: 90 ms

Insercion: 60 ms

std::sort: 1500 us (1.5 ms)

🧪 9. LAB 3.6 — Comparador Visual de Algoritmos (5 h)

Descripción

Crea un programa que:

1. Genere arreglos aleatorios de tamaños 100, 1 000, 10 000.
2. Implemente los 3 algoritmos (burbuja, selección, inserción).
3. Mida el tiempo de cada uno con cada tamaño.
4. Imprima una tabla con: tamaño, burbuja (ms), selección (ms), inserción (ms), sort (μs).
5. Visualización: muestre paso a paso cómo va quedando el arreglo en el algoritmo de inserción (solo con n=10 para que se vea).
6. Modo interactivo: permita al usuario ingresar su propio arreglo y elegir el algoritmo.

Rúbrica de evaluación

Bonus XP

• +30 XP si agregas Quicksort (algoritmo O(n log n) recursivo).
• +20 XP si la visualización usa colores en consola (Windows: SetConsoleTextAttribute).
• +20 XP si graficas los resultados con un histograma de barras ASCII.
• +10 XP si comparas con un arreglo ya ordenado (para mostrar que inserción es O(n) en ese caso).

🔚 11. Cierre — Cuaderno del programador

1. Traza los 3 algoritmos con [3, 1, 4, 1, 5] en tu cuaderno. Anota el número de comparaciones de cada uno.
2. Dibuja una analogía para cada algoritmo:

• Burbuja: comparar tarjetas adyacentes
• Selección: buscar el más pequeño y colocarlo
• Inserción: tomar cartas de una baraja e ir insertándolas

1. Reflexión: ¿cuál te costó más entender? ¿Por qué?
2. Compromiso: la próxima vez que ordenes, primero pregúntate si el lenguaje ya tiene `sort`. Si sí, úsalo. Si no, escoge el algoritmo según el caso.

🏅 Insignia y XP del tema

🔗 ¿Qué sigue?

Tema 3.7 — Struct y Archivos. Aprende a agrupar datos heterogéneos en una sola unidad (struct) y a persistir información en archivos. Hasta ahora, todo se pierde al cerrar el programa. Aquí lo cambias: el programa recuerda entre ejecuciones.

Antes de avanzar:

• [ ] LAB 3.6 entregado y funcionando
• [ ] Quest mixto respondido en el cuaderno
• [ ] Reflexión escrita

*"No necesitas escribir el mejor sort. Necesitas saber cuál existe y cuándo usarlo."*

⚠️ Errores típicos — ⚠️ 8. Errores típicos del razonamiento

Error 1: Confundir los límites del bucle exterior

// Burbuja

for (int i = 0; i < n; i++)  // MAL: n pasadas
for (int i = 0; i < n - 1; i++)  // BIEN: n-1 (la última es trivial)

Con n = 1, no hay nada que ordenar. Con n = 5, basta con 4 pasadas.

Error 2: Olvidar que el rango se reduce

for (int j = 0; j < n; j++)  // MAL: compara con todo siempre
for (int j = 0; j < n - 1 - i; j++)  // BIEN: ignora la parte ya ordenada

En la pasada i, los últimos i elementos ya están en su lugar.

Error 3: En selección, olvidar el if (posMin != i)

swap(arr[i], arr[posMin]); // MAL si posMin == i (hace swap consigo mismo, no rompe pero...)

if (posMin != i) swap(arr[i], arr[posMin]);  // BIEN, ahorra una operación

Error 4: En inserción, empezar el while desde j + 1

while (j >= 0 && arr[j] > actual) {

arr[j] = actual; // MAL: sobreescribe el valor

arr[j + 1] = arr[j]; // BIEN: desplaza

j--;

}

La operación de inserción es desplazar a la derecha, no copiar el valor nuevo.

Error 5: Asumir que "más complejo = más rápido"

// Código ultra-optimizado con 3 loops anidados y flags

// vs std::sort()

sort(arr, arr + n);

La simplicidad no es enemiga de la eficiencia cuando usas buenas librerías.

🤖 IA como copiloto — 🤖 7. AI Mission — "Dame la traza, no el código"

Objetivo: usar la IA para verificar tu traza manual, no para que la haga por ti.

Escenario: terminaste el algoritmo de selección, pero no estás seguro si el ciclo interior debe ir hasta n o hasta n-1.

Prompt sugerido:

"Tengo este código en C++ del ordenamiento por selección. Explícame por qué el `for` interior va de `i+1` hasta `n` y no hasta `n-1`. No me des código nuevo, solo explícame el rango con un ejemplo de n=5."

Lo que NO debes hacer:

• Pedirle una implementación optimizada (mejor usa std::sort).
• Copiar la explicación sin trazar tú mismo el ejemplo.

Lo que SÍ debes hacer:

• Trazar el algoritmo con n=5 y 3 elementos.
• Escribir la explicación de la IA con tus palabras en el cuaderno.

Ritual de 3 min: si la IA te da una explicación confusa, trazar otro ejemplo en lugar de pedirle otra explicación.

📝 Quest · Cuestionario — 📝 Quest — Reactivos para autoevaluación

Sección A · Opción múltiple

Elige la opción correcta (A, B, C o D). Las respuestas están en la sección Respuestas modelo.

1. ¿Cómo funciona el ordenamiento por burbuja?
   • Selecciona el menor
   • Compara pares adyacentes e intercambia si están en orden incorrecto
   • Usa hash
   • Divide y vencerás
2. ¿Cuál es la complejidad del ordenamiento por burbuja?
   • O(n)
   • O(n²)
   • O(log n)
   • O(n log n)
3. ¿Cómo funciona el ordenamiento por selección?
   • Compara adyacentes
   • Selecciona el menor y lo coloca en su posición
   • Divide
   • Usa hash
4. ¿Cómo funciona el ordenamiento por inserción?
   • Selecciona
   • Inserta cada elemento en su lugar correcto dentro de los ya ordenados
   • Divide
   • Hash
5. ¿Cuál es la complejidad del ordenamiento por inserción?
   • Siempre O(n²)
   • O(n) en mejor caso (casi ordenado), O(n²) peor caso
   • O(log n)
   • O(n log n)
6. ¿Qué algoritmo de ordenamiento es O(n log n) en el peor caso?
   • Burbuja
   • Selección
   • Mergesort
   • Inserción
7. Quicksort en el peor caso es:
   • O(n)
   • O(n log n) en promedio, O(n²) en el peor caso
   • O(log n)
   • O(n²) siempre
8. Un ordenamiento estable preserva:
   • El orden de elementos iguales
   • La velocidad
   • El tipo de datos
   • El uso de memoria
9. ¿Cuál de estos es estable?
   • Quicksort clásico
   • Mergesort e Inserción
   • Heapsort
   • Selección
10. Para ordenar 1 millón de números, ¿cuál es típicamente más rápido?
    • Burbuja
    • Mergesort o Quicksort
    • Inserción
    • Selección

Sección B · Preguntas abiertas

Desarrolla tu respuesta en al menos 3 líneas. Compara con la respuesta modelo después de escribir.

1. Compara ordenamiento estable vs inestable. Da un ejemplo donde importa la estabilidad.
   → Escribe tu respuesta aquí (en tu cuaderno o mentalmente)…
2. ¿Cuándo usarías ordenamiento por inserción sobre Quicksort? Da 2 razones.
   → Escribe tu respuesta aquí (en tu cuaderno o mentalmente)…
3. Diseña un algoritmo que verifique si un arreglo está ordenado. ¿Complejidad?
   → Escribe tu respuesta aquí (en tu cuaderno o mentalmente)…