Bubble sort
Última atualização
O bubble sort percorre a lista repetidamente, compara cada par de elementos adjacentes e os troca se estiverem na ordem errada. Após cada passagem completa, o maior valor restante "borbulhou" até sua posição correta no final, então cada passagem examina um elemento a menos. Pressione reproduzir acima para ver as comparações e trocas, ou avance por elas uma de cada vez.
É um dos algoritmos de ordenação mais fáceis de entender, o que o torna um ótimo primeiro algoritmo, mas seu tempo de execução O(n²) o torna impraticável para entradas grandes.
Complexidade de tempo e espaço
| Caso | Complexidade | Notas |
|---|---|---|
| Melhor caso | O(n) | Já ordenado, com uma verificação de saída antecipada |
| Caso médio | O(n²) | Ordem aleatória |
| Pior caso | O(n²) | Ordenado ao contrário |
| Espaço | O(1) | No local, apenas uma variável temporária |
| Estável | Sim | Elementos iguais mantêm sua ordem relativa |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Comece no início do arranjo. |
| 2 | Compare o elemento atual com o próximo. |
| 3 | Se estiverem fora de ordem, troque-os. |
| 4 | Avance uma posição à direita e repita até o final (uma passagem). |
| 5 | Repita as passagens; cada passagem fixa mais um elemento no final. |
| 6 | Pare quando uma passagem completa não fizer trocas. |
Exemplo resolvido
Ordenando [5, 2, 4, 1]:
| Passagem | Arranjo | Ação |
|---|---|---|
| 1 | [2, 4, 1, 5] | Troca 5,2, depois 5,4, depois 5,1; o 5 borbulha até o final. |
| 2 | [2, 1, 4, 5] | 2,4 em ordem; troca 4,1; 4,5 em ordem; o 4 fica posicionado. |
| 3 | [1, 2, 4, 5] | Troca 2,1; o restante já está em ordem; o 2 fica posicionado. |
| 4 | [1, 2, 4, 5] | Uma passagem completa não faz trocas, então o arranjo está ordenado e o algoritmo para. |
Quando usar o bubble sort
| Use quando | Evite quando |
|---|---|
| Está ensinando ou aprendendo como funcionam as ordenações por comparação | Está ordenando entradas grandes, onde O(n²) é lento demais |
A entrada é minúscula ou quase ordenada (com saída antecipada se aproxima de O(n)) | Você precisa da ordenação de propósito geral mais rápida: use quicksort ou merge sort |
| Você precisa de uma ordenação estável, no local e com quase nenhum código | Os dados estão em ordem aleatória e o desempenho importa |
| Está detectando se uma lista curta já está ordenada em uma única passagem | Muitas escritas são caras (p. ex. memória flash); a ordenação por seleção faz menos trocas |
Código de Bubble Sort
Uma implementação limpa e executável de Bubble Sort em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Bubble Sort em Python
Python
1def bubble_sort(a):2 n = len(a)3 for i in range(n - 1):4 swapped = False5 for j in range(n - 1 - i):6 if a[j] > a[j + 1]:7 a[j], a[j + 1] = a[j + 1], a[j]8 swapped = True9 if not swapped:10 break # no swaps means the list is already sorted11 return a12
13
14nums = [5, 1, 4, 2, 8]15print("Before:", nums)16bubble_sort(nums)17print("After: ", nums)Código de Bubble Sort em JavaScript
JavaScript
1function bubbleSort(a) {2 for (let end = a.length - 1; end > 0; end--) {3 let swapped = false;4 for (let j = 0; j < end; j++) {5 if (a[j] > a[j + 1]) {6 [a[j], a[j + 1]] = [a[j + 1], a[j]];7 swapped = true;8 }9 }10 if (!swapped) break; // Already sorted: stop early11 }12 return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", bubbleSort([...data]));Código de Bubble Sort em Java
Java
1import java.util.Arrays;2
3public class Main {4 static void bubbleSort(int[] arr) {5 for (int i = arr.length - 1; i > 0; i--) {6 boolean swapped = false;7 for (int j = 0; j < i; j++) {8 if (arr[j] > arr[j + 1]) {9 int tmp = arr[j];10 arr[j] = arr[j + 1];11 arr[j + 1] = tmp;12 swapped = true;13 }14 }15 if (!swapped) break; // already sorted16 }17 }18
19 public static void main(String[] args) {20 int[] arr = {5, 1, 4, 2, 8, 3};21 System.out.println("Before: " + Arrays.toString(arr));22 bubbleSort(arr);23 System.out.println("After: " + Arrays.toString(arr));24 }25}Código de Bubble Sort em C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void bubbleSort(std::vector<int>& a) {11 for (size_t pass = 0; pass + 1 < a.size(); ++pass) {12 bool swapped = false;13 // Each pass bubbles the largest remaining value to the end14 for (size_t j = 0; j + 1 < a.size() - pass; ++j) {15 if (a[j] > a[j + 1]) {16 std::swap(a[j], a[j + 1]);17 swapped = true;18 }19 }20 if (!swapped) break; // already sorted21 }22}23
24int main() {25 std::vector<int> data = {5, 1, 4, 2, 8, 3};26 std::cout << "Before: ";27 printVec(data);28 bubbleSort(data);29 std::cout << "After: ";30 printVec(data);31 return 0;32}Código de Bubble Sort em C
C
1#include <stdbool.h>2#include <stdio.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9void bubbleSort(int a[], int n) {10 for (int pass = 0; pass < n - 1; pass++) {11 bool swapped = false;12 // Each pass bubbles the largest remaining value to the end13 for (int j = 0; j < n - 1 - pass; j++) {14 if (a[j] > a[j + 1]) {15 int tmp = a[j];16 a[j] = a[j + 1];17 a[j + 1] = tmp;18 swapped = true;19 }20 }21 if (!swapped) break; // already sorted22 }23}24
25int main(void) {26 int data[] = {5, 1, 4, 2, 8, 3};27 int n = sizeof(data) / sizeof(data[0]);28 printf("Before: ");29 printArr(data, n);30 bubbleSort(data, n);31 printf("After: ");32 printArr(data, n);33 return 0;34}Perguntas frequentes sobre o bubble sort
Qual é a complexidade de tempo do bubble sort?
O bubble sort é executado em tempo
O(n²) nos casos médio e pior por causa dos laços aninhados. Com uma otimização de saída antecipada pode alcançar O(n) em um arranjo já ordenado. Usa O(1) de espaço extra.O bubble sort é estável?
Sim. O bubble sort só troca elementos adjacentes quando estão estritamente fora de ordem, então elementos iguais nunca se ultrapassam e mantêm sua ordem relativa original.
Por que se chama bubble sort?
Em cada passagem o maior valor não ordenado move-se passo a passo em direção ao final do arranjo, como uma bolha que sobe à superfície, daí o nome "bubble" (bolha).
Qual é a diferença entre bubble sort e insertion sort?
Ambos são executados em
O(n²) e são estáveis e no local, mas movem os dados de forma diferente: o bubble sort troca repetidamente pares adjacentes fora de ordem, enquanto o insertion sort pega cada elemento e o desliza até seu lugar correto no prefixo ordenado. O insertion sort geralmente faz menos escritas e é mais rápido na prática, especialmente com dados quase ordenados.Quando devo usar o bubble sort em vez do quicksort?
Quase nunca em cargas de trabalho reais: o tempo médio
O(n log n) do quicksort esmaga o O(n²) do bubble sort em tudo, exceto entradas minúsculas. O bubble sort só vale a pena quando a lista é muito pequena ou quase ordenada, ou quando você quer a ordenação estável mais simples possível para ensinar.A otimização de saída antecipada muda o pior caso do bubble sort?
Não. Registrar se uma passagem fez alguma troca permite ao bubble sort parar cedo e alcançar
O(n) em entradas já ordenadas, mas um arranjo ordenado ao contrário ainda precisa de todas as comparações, então o pior caso continua O(n²). A otimização só ajuda no melhor caso e nos quase ordenados.Recursos relacionados
Mais visualizações
