Ordenação e recursão

Ordenação

Bubble sort — O(n²)

O mais simples de entender: compara pares adjacentes e os troca se estiverem na ordem incorreta, repetindo até que não haja mudanças.

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 e quick sort — O(n log n)

Para dados grandes, usam-se algoritmos de dividir para conquistar:

• Merge sort: divide o array ao meio, ordena cada metade e as funde ordenadas.
• Quick sort: escolhe um pivô, coloca de um lado os menores e do outro os maiores, e repete em cada lado.

Ambos são muito mais rápidos que o bubble sort para entradas grandes. Na prática, Array.prototype.sort() já usa um algoritmo eficiente.

Recursão

Uma função recursiva chama a si mesma com um problema menor até chegar a um 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);
}

O fibonacci recursivo ingênuo é O(2ⁿ): recalcula os mesmos valores uma e outra vez. Pode ser otimizado com memoização ou com um laço.

Exemplos

Bubble sort com rastreamento

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]));

Fatorial recursivo

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