Olá pessoal! Na aula de hoje vamos mergulhar nos algoritmos de ordenação, um pilar fundamental da computação. Ordenar dados está na base de buscas eficientes, organização de registos, compressão e muitas outras aplicações. Começaremos pelos três algoritmos mais didáticos — Bubble Sort, Insertion Sort e Selection Sort — que introduzem conceitos importantes como complexidade assintótica, invariantes de loop e estabilidade.

1. O que são algoritmos de ordenação?

Um algoritmo de ordenação recebe uma sequência de elementos e rearranja seus itens de acordo com uma relação de ordem predefinida (geralmente crescente ou decrescente). A eficiência de cada algoritmo é medida pelo número de comparações e trocas realizadas, expressa pela notação Big-O.

Antes de analisar cada um, vale lembrar o essencial da notação O grande: ela descreve o comportamento do tempo de execução conforme o tamanho da entrada (n) cresce. Todos os três algoritmos que veremos hoje têm complexidade O(n²) no pior caso, mas se comportam de maneiras diferentes em entradas pequenas ou quase ordenadas.

2. Bubble Sort

O Bubble Sort percorre a lista repetidamente, comparando elementos adjacentes e trocando‑os se estiverem na ordem errada. A cada passagem, o maior elemento “flutua” para a posição final — daí o nome “bolha”.

Exemplo com [5,3,8,4,2]:

  1. 1ª passagem: [3,5,4,2,8] (8 já no lugar)
  2. 2ª passagem: [3,4,2,5,8]
  3. 3ª passagem: [3,2,4,5,8]
  4. 4ª passagem: [2,3,4,5,8]

Podemos otimizar o algoritmo parando a execução se nenhuma troca for realizada em uma passagem completa. Com essa melhoria, o melhor caso (lista já ordenada) se torna O(n).

function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        if (!swapped) break;
    }
    return arr;
}

Complexidade: O(n) melhor caso (otimizado), O(n²) pior caso.

3. Insertion Sort

O Insertion Sort constrói a lista ordenada incrementalmente. Imagine que você está organizando cartas de baralho: a cada nova carta, você a insere na posição correta em relação às cartas já ordenadas.

Processo: para cada elemento i (do segundo ao último), salvamos seu valor (chave) e deslocamos para a direita todos os elementos da parte ordenada maiores que a chave, abrindo espaço para inseri‑la.

Exemplo com [5,3,8,4,2]:

  1. i=1 (chave=3) → [3,5,8,4,2]
  2. i=2 (chave=8) → [3,5,8,4,2] (já no lugar)
  3. i=3 (chave=4) → [3,4,5,8,2]
  4. i=4 (chave=2) → [2,3,4,5,8]
function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

Complexidade: O(n) melhor caso (lista ordenada), O(n²) pior caso. É estável e excelente para listas parcialmente ordenadas.

4. Selection Sort

O Selection Sort divide a lista em duas partes: a região ordenada (no início) e a não ordenada. A cada passo, seleciona o menor elemento da parte não ordenada e o troca com o primeiro elemento dessa região, expandindo a parte ordenada.

Exemplo com [5,3,8,4,2]:

  1. Menor=2 → troca com 5: [2,3,8,4,5]
  2. Menor=3 → já no lugar: [2,3,8,4,5]
  3. Menor=4 → troca com 8: [2,3,4,8,5]
  4. Menor=5 → troca com 8: [2,3,4,5,8]
function selectionSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let minIdx = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        if (minIdx !== i) {
            [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
        }
    }
    return arr;
}

Complexidade: O(n²) em todos os casos (não possui melhor/pior caso distinto). Realiza no máximo O(n) trocas, o que pode ser vantajoso quando escrever em memória é caro.

5. Comparação detalhada

AlgoritmoMelhor casoPior casoEstávelIn‑place
Bubble SortO(n) (otimizado)O(n²)SimSim
Insertion SortO(n)O(n²)SimSim
Selection SortO(n²)O(n²)NãoSim

Ser estável significa que elementos iguais preservam a ordem relativa original. Isso é importante em ordenações múltiplas (por exemplo, ordenar por data e depois por nome).

6. Vantagens e desvantagens

  • Bubble Sort: muito simples de implementar, mas lento para listas grandes; a versão otimizada pode ser eficiente em listas quase ordenadas.
  • Insertion Sort: rápido para listas pequenas (<~50 elementos) e parcialmente ordenadas; estável; é usado como parte do Timsort (algoritmo nativo do Python e do Java).
  • Selection Sort: número mínimo de trocas (O(n)); porém não é estável e sempre realiza O(n²) comparações.

7. Quando usar cada um na prática?

Em aplicações reais, preferimos algoritmos mais rápidos como QuickSort, MergeSort ou o Timsort para grandes conjuntos. O Insertion Sort, no entanto, é frequentemente usado internamente para ordenar pequenas partições em algoritmos híbridos. Bubble Sort e Selection Sort são predominantemente didáticos — fundamentais para entender os conceitos, mas não recomendados para produção.

Perguntas frequentes (FAQ)

  • Qual a principal diferença entre Insertion Sort e Selection Sort?
    O Insertion Sort insere cada elemento na posição correta deslocando os maiores; o Selection Sort seleciona o menor e o coloca no início. Insertion é estável; Selection não.
  • Bubble Sort pode ser útil em algum cenário real?
    Raramente. Em sistemas que exigem simplicidade absoluta e listas muito pequenas, pode ser usado. Mas algoritmos como Insertion Sort são superiores com o mesmo nível de simplicidade.
  • O que significa “in‑place”?
    Significa que o algoritmo ordena a lista usando apenas uma quantidade constante de espaço extra (não cria arrays auxiliares proporcionais ao tamanho da entrada).
  • Algum desses algoritmos é usado no dia a dia do programador?
    O Insertion Sort é a base do Timsort, e o Selection Sort (ou variações) aparece em problemas onde o custo de troca é muito alto. Mas para a maioria dos casos, linguagens já oferecem funções prontas (como .sort() em Python/JavaScript) que implementam algoritmos otimizados.

Espero que a aula tenha esclarecido os fundamentos dos algoritmos de ordenação. Na próxima aula avançaremos para estratégias mais eficientes como Merge Sort e Quick Sort. Até lá!