Tabla de contenido

Si las estructuras de datos son las formas de organizar información, los algoritmos son las recetas para procesarla. Dos de las familias más importantes son los algoritmos de búsqueda (encontrar un elemento) y de ordenamiento (poner elementos en orden).

¿Qué es la complejidad algorítmica?

Antes de ver el código, necesitamos un vocabulario básico: la notación Big O describe cuánto tiempo o espacio necesita un algoritmo en función del tamaño del input (n).

  • O(1): tiempo constante, no importa el tamaño del input
  • O(log n): logarítmico, muy eficiente (duplicar el input solo agrega un paso)
  • O(n): lineal, crece proporcional al input
  • O(n²): cuadrático, muy lento para datos grandes

Búsqueda Lineal

La búsqueda lineal revisa cada elemento uno por uno hasta encontrar el que busca. Es el algoritmo más simple pero también el menos eficiente.

Complejidad: O(n) — en el peor caso, revisa todos los elementos.

function busquedaLineal(arreglo, objetivo) {
  for (let i = 0; i < arreglo.length; i++) {
    if (arreglo[i] === objetivo) {
      return i; // retorna el índice donde encontró el elemento
    }
  }
  return -1; // retorna -1 si no lo encontró
}

const numeros = [4, 2, 7, 1, 9, 3, 8, 5];

console.log(busquedaLineal(numeros, 9));  // 4 (posición del 9)
console.log(busquedaLineal(numeros, 6));  // -1 (no existe)

¿Cuándo usarla? Cuando el arreglo es pequeño o no está ordenado. No hay forma de mejorarla para arreglos desordenados.

Búsqueda Binaria

La búsqueda binaria es mucho más eficiente, pero requiere que el arreglo esté ordenado. El algoritmo divide el arreglo a la mitad en cada paso: compara el elemento del medio con el objetivo y decide si buscar en la mitad izquierda o derecha.

Complejidad: O(log n) — en un millón de elementos, hace máximo ~20 comparaciones.

function busquedaBinaria(arreglo, objetivo) {
  let inicio = 0;
  let fin = arreglo.length - 1;
  
  while (inicio <= fin) {
    const medio = Math.floor((inicio + fin) / 2);
    
    if (arreglo[medio] === objetivo) {
      return medio; // encontrado
    } else if (arreglo[medio] < objetivo) {
      inicio = medio + 1; // buscar en la mitad derecha
    } else {
      fin = medio - 1; // buscar en la mitad izquierda
    }
  }
  
  return -1; // no encontrado
}

const ordenado = [1, 3, 5, 7, 9, 12, 15, 18, 21, 25];

console.log(busquedaBinaria(ordenado, 12)); // 5
console.log(busquedaBinaria(ordenado, 10)); // -1

// Comparación de eficiencia para 1,000,000 elementos:
// Búsqueda lineal: hasta 1,000,000 comparaciones
// Búsqueda binaria: máximo 20 comparaciones

Visualización mental:

Buscamos 12 en: [1, 3, 5, 7, 9, 12, 15, 18, 21, 25]
                                  ^--- medio = 9

9 < 12: buscamos en la derecha: [12, 15, 18, 21, 25]
                                      ^--- medio = 18

18 > 12: buscamos en la izquierda: [12, 15]
                                        ^--- medio = 12

¡Encontrado en 3 pasos! En binaria logramos que 1M de elementos solo necesite ~20 pasos

Bubble Sort

Bubble Sort es el algoritmo de ordenamiento más didáctico. Compara pares de elementos adyacentes e intercambia los que están en el orden incorrecto. Repite esto hasta que todo esté ordenado.

Complejidad: O(n²) — muy lento para arreglos grandes, pero útil para aprender.

function bubbleSort(arreglo) {
  const n = arreglo.length;
  const arr = [...arreglo]; // copia para no modificar el original
  
  for (let i = 0; i < n - 1; i++) {
    let huboIntercambio = false;
    
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // intercambiar
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        huboIntercambio = true;
      }
    }
    
    // Optimización: si no hubo intercambios, ya está ordenado
    if (!huboIntercambio) break;
  }
  
  return arr;
}

const desordenado = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(desordenado)); 
// [11, 12, 22, 25, 34, 64, 90]

Paso a paso para [5, 3, 8, 1]:

Pasada 1: [3, 5, 8, 1] → [3, 5, 1, 8]
Pasada 2: [3, 1, 5, 8]
Pasada 3: [1, 3, 5, 8] ✅

Selection Sort

Selection Sort busca el elemento mínimo y lo coloca al inicio, luego el siguiente mínimo, y así hasta ordenar todo.

Complejidad: O(n²) — similar a Bubble Sort, pero hace menos intercambios.

function selectionSort(arreglo) {
  const arr = [...arreglo];
  const n = arr.length;
  
  for (let i = 0; i < n - 1; i++) {
    let indiceMenor = i;
    
    // Buscar el menor en el resto del arreglo
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[indiceMenor]) {
        indiceMenor = j;
      }
    }
    
    // Intercambiar el menor con la posición actual
    if (indiceMenor !== i) {
      [arr[i], arr[indiceMenor]] = [arr[indiceMenor], arr[i]];
    }
  }
  
  return arr;
}

const numeros = [29, 10, 14, 37, 13];
console.log(selectionSort(numeros));
// [10, 13, 14, 29, 37]

Métodos nativos vs algoritmos propios

En la práctica, nunca implementarás Bubble Sort en producción. Los lenguajes modernos tienen métodos de ordenamiento nativos muy optimizados:

// JavaScript nativo - usa TimSort (O(n log n))
const arr = [64, 34, 25, 12, 22, 11, 90];
arr.sort((a, b) => a - b); // ascendente
arr.sort((a, b) => b - a); // descendente

// Ordenar objetos por propiedad
const usuarios = [
  { nombre: "Brenda", edad: 28 },
  { nombre: "Abraham", edad: 25 },
  { nombre: "Carlos", edad: 31 },
];

usuarios.sort((a, b) => a.edad - b.edad);
// [Abraham(25), Brenda(28), Carlos(31)]

Entonces, ¿para qué aprender Bubble Sort? Porque entender estos algoritmos te enseña a pensar sobre la eficiencia, a analizar problemas paso a paso, y a comunicarte en entrevistas técnicas. La base conceptual es invaluable aunque no los uses directamente.