Ordenación y recursión

Ordenación

Bubble sort — O(n²)

El más sencillo de entender: compara pares adyacentes y los intercambia si están en el orden incorrecto, repitiendo hasta que no haya cambios.

function bubbleSort(arr) {
  const a = [...arr];
  for (let i = 0; i < a.length; i++) {
    for (let j = 0; j < a.length - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
      }
    }
  }
  return a;
}

Merge sort y quick sort — O(n log n)

Para datos grandes se usan algoritmos divide y vencerás:

• Merge sort: divide el array por la mitad, ordena cada mitad y las fusiona ordenadas.
• Quick sort: elige un pivote, coloca a un lado los menores y al otro los mayores, y repite en cada lado.

Ambos son mucho más rápidos que bubble sort para entradas grandes. En la práctica, Array.prototype.sort() ya usa un algoritmo eficiente.

Recursión

Una función recursiva se llama a sí misma con un problema más pequeño hasta llegar a un caso base.

function factorial(n) {
  if (n <= 1) return 1;       // caso base
  return n * factorial(n - 1); // caso recursivo
}

function fibonacci(n) {
  if (n < 2) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

El fibonacci recursivo ingenuo es O(2ⁿ): recalcula los mismos valores una y otra vez. Se puede optimizar con memorización o con un bucle.

Ejemplos

Bubble sort con traza

function bubbleSort(arr) {
  const a = [...arr];
  for (let i = 0; i < a.length; i++) {
    for (let j = 0; j < a.length - 1 - i; j++) {
      if (a[j] > a[j + 1]) [a[j], a[j + 1]] = [a[j + 1], a[j]];
    }
  }
  return a;
}
console.log(bubbleSort([5, 2, 8, 1, 9, 3]));

Factorial recursivo

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}
console.log("5! =", factorial(5));