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ª passagem: [3,5,4,2,8] (8 já no lugar)
- 2ª passagem: [3,4,2,5,8]
- 3ª passagem: [3,2,4,5,8]
- 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]:
- i=1 (chave=3) → [3,5,8,4,2]
- i=2 (chave=8) → [3,5,8,4,2] (já no lugar)
- i=3 (chave=4) → [3,4,5,8,2]
- 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]:
- Menor=2 → troca com 5: [2,3,8,4,5]
- Menor=3 → já no lugar: [2,3,8,4,5]
- Menor=4 → troca com 8: [2,3,4,8,5]
- 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
| Algoritmo | Melhor caso | Pior caso | Estável | In‑place |
|---|---|---|---|---|
| Bubble Sort | O(n) (otimizado) | O(n²) | Sim | Sim |
| Insertion Sort | O(n) | O(n²) | Sim | Sim |
| Selection Sort | O(n²) | O(n²) | Não | Sim |
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á!