Bubble Sort
Os elementos maiores "borbulham" para o final — comparando e trocando pares adjacentes repetidamente até a lista estar ordenada.
O(n²)O(1)Como Funciona
Passo a passo do algoritmo
Percorra o array comparando pares
Comece do primeiro elemento e compare cada par adjacente. Se o elemento da esquerda for maior que o da direita, troque-os de posição.
para j de 0 até n-i-2: se array[j] > array[j+1]: troca(j, j+1)O maior elemento "borbulha" para o final
Após cada passagem completa pelo array, o maior elemento não ordenado estará em sua posição definitiva no final. Este elemento não precisa ser comparado nas próximas passagens.
// Após passagem i: array[n-i..n-1] está ordenadoRepita para o restante
Faça novas passagens pelo array, mas cada vez comparando um elemento a menos no final (pois eles já estão ordenados).
para i de 0 até n-1: percorrer até n-i-1Otimização com flag de troca
Se uma passagem completa acontecer sem nenhuma troca, o array já está ordenado. Esta otimização melhora o caso de listas quase ordenadas para O(n).
se nenhuma_troca: interromperImplementação
Código comentado em JavaScript e Python
function bubbleSort(array) {
const n = array.length;
for (let i = 0; i < n - 1; i++) {
let trocou = false; // Otimização: detectar array já ordenado
// Cada passagem move o maior elemento não ordenado para o final
for (let j = 0; j < n - i - 1; j++) {
if (array[j] > array[j + 1]) {
// Troca os elementos fora de ordem
[array[j], array[j + 1]] = [array[j + 1], array[j]];
trocou = true;
}
}
// Se não houve troca, array já está ordenado
if (!trocou) break;
}
return array;
}
// Exemplo de uso
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr)); // [11, 12, 22, 25, 34, 64, 90]Playground
Veja os elementos 'borbulhando' até suas posições corretas
Quando Usar
Cenários ideais para este algoritmo
Aprendizado e ensino
Algoritmo ideal para introduzir conceitos de ordenação — lógica simples e visualização intuitiva das trocas.
Listas quase ordenadas
Com a otimização de flag, é eficiente para arrays que já estão quase ordenados, chegando a O(n) no melhor caso.
Detectar se está ordenado
Útil quando você precisa verificar se uma lista está ordenada e ordenar caso não esteja, com uma única passagem.
Listas muito pequenas
O overhead baixo de implementação torna o Bubble Sort prático para listas de poucos elementos onde a complexidade não importa.
Complexidade
Análise de desempenho por cenário
| Cenário | Tempo |
|---|---|
| Melhor caso | O(n) |
| Caso médio | O(n²) |
| Pior caso | O(n²) |