O que é Bubble Sort?
O Bubble Sort é um algoritmo de ordenação simples que funciona comparando elementos adjacentes e trocando-os se estiverem na ordem errada. O nome vem do fato de que os elementos menores "borbulham" para o início da lista, assim como bolhas de ar sobem para a superfície da água.
Como funciona?
O algoritmo funciona da seguinte forma:
- Compara elementos adjacentes no array
- Troca os elementos se estiverem na ordem errada (o maior vai para a direita)
- Repete o processo para todos os pares adjacentes
- Continua as iterações até que nenhuma troca seja necessária
Diagramação
Configura aqui
Exemplo Visual
Considerando o array: [64, 34, 25, 12, 22, 11, 90]
Iteração 1:
- Compara 64 e 34:
64 > 34→ Troca:[34, 64, 25, 12, 22, 11, 90] - Compara 64 e 25:
64 > 25→ Troca:[34, 25, 64, 12, 22, 11, 90] - Compara 64 e 12:
64 > 12→ Troca:[34, 25, 12, 64, 22, 11, 90] - Compara 64 e 22:
64 > 22→ Troca:[34, 25, 12, 22, 64, 11, 90] - Compara 64 e 11:
64 > 11→ Troca:[34, 25, 12, 22, 11, 64, 90] - Compara 64 e 90:
64 < 90→ Sem troca:[34, 25, 12, 22, 11, 64, 90] - Resultado: O maior elemento (90) está na posição correta
Iteração 2:
- Compara 34 e 25:
34 > 25→ Troca:[25, 34, 12, 22, 11, 64, 90] - Compara 34 e 12:
34 > 12→ Troca:[25, 12, 34, 22, 11, 64, 90] - Compara 34 e 22:
34 > 22→ Troca:[25, 12, 22, 34, 11, 64, 90] - Compara 34 e 11:
34 > 11→ Troca:[25, 12, 22, 11, 34, 64, 90] - Compara 34 e 64:
34 < 64→ Sem troca - Resultado: Os dois maiores elementos estão nas posições corretas
Iteração 3:
- Compara 25 e 12:
25 > 12→ Troca:[12, 25, 22, 11, 34, 64, 90] - Compara 25 e 22:
25 > 22→ Troca:[12, 22, 25, 11, 34, 64, 90] - Compara 25 e 11:
25 > 11→ Troca:[12, 22, 11, 25, 34, 64, 90] - Compara 25 e 34:
25 < 34→ Sem troca
O processo continua até que nenhuma troca seja necessária, resultando em: [11, 12, 22, 25, 34, 64, 90]
Implementação
Nossa implementação educativa inclui saídas detalhadas para ajudar no aprendizado.
Você pode encontrar uma implementação completa e educativa do Bubble Sort em:
- 📁 Domus/Domus-1/bubbleSort.cpp
Função Principal - Bubble Sort Algorithm
void bubbleSortAlgorithm(int dataArray[], int arraySize)
{
cout << "========================================" << endl;
cout << "STARTING BUBBLE SORT ALGORITHM" << endl;
cout << "========================================" << endl;
cout << "Initial array: ";
for(int displayIndex = 0; displayIndex < arraySize; displayIndex++) {
cout << dataArray[displayIndex] << " ";
}
cout << endl << endl;
int totalNumberOfSwaps = 0;
int totalNumberOfComparisons = 0;
bool hasSwapped = true;
int iterationCount = 0;
while (hasSwapped && iterationCount < arraySize - 1)
{
iterationCount++;
hasSwapped = false;
cout << ">>> ITERATION " << iterationCount << " <<<" << endl;
cout << "Comparing adjacent elements..." << endl;
for (int currentIndex = 0; currentIndex < arraySize - iterationCount; currentIndex++)
{
int nextIndex = currentIndex + 1;
totalNumberOfComparisons++;
cout << "Comparing dataArray[" << currentIndex << "] = " << dataArray[currentIndex]
<< " with dataArray[" << nextIndex << "] = " << dataArray[nextIndex];
if (dataArray[currentIndex] > dataArray[nextIndex]) {
cout << " -> " << dataArray[currentIndex] << " > " << dataArray[nextIndex]
<< ", need to swap!" << endl;
swapElements(dataArray, currentIndex, nextIndex);
hasSwapped = true;
totalNumberOfSwaps++;
} else {
cout << " -> " << dataArray[currentIndex] << " <= " << dataArray[nextIndex]
<< ", no swap needed" << endl;
}
}
cout << "Array state after iteration " << iterationCount << ": ";
for(int displayIndex = 0; displayIndex < arraySize; displayIndex++) {
if (displayIndex >= arraySize - iterationCount) {
cout << "[" << dataArray[displayIndex] << "] "; // Already sorted elements
} else {
cout << dataArray[displayIndex] << " "; // Not yet sorted elements
}
}
cout << endl;
cout << "Elements in final position: " << iterationCount << "/" << arraySize << endl;
if (!hasSwapped) {
cout << "No swaps performed in this iteration - array is sorted!" << endl;
}
cout << "--------------------------------" << endl;
}
cout << "========================================" << endl;
cout << "BUBBLE SORT ALGORITHM COMPLETED!" << endl;
cout << "Total number of iterations: " << iterationCount << endl;
cout << "Total number of comparisons: " << totalNumberOfComparisons << endl;
cout << "Total number of swaps performed: " << totalNumberOfSwaps << endl;
cout << "========================================" << endl;
}
Função para Trocar Elementos
void swapElements(int dataArray[], int firstPosition, int secondPosition)
{
cout << " -> Swapping elements: " << dataArray[firstPosition] << " (position " << firstPosition << ") <-> " << dataArray[secondPosition] << " (position " << secondPosition << ")" << endl;
int temporaryValue = dataArray[firstPosition];
dataArray[firstPosition] = dataArray[secondPosition];
dataArray[secondPosition] = temporaryValue;
cout << " -> After swap: position " << firstPosition << " = " << dataArray[firstPosition] << ", position " << secondPosition << " = " << dataArray[secondPosition] << endl;
}
Versão Otimizada do Bubble Sort
void optimizedBubbleSortAlgorithm(int dataArray[], int arraySize)
{
cout << "========================================" << endl;
cout << "STARTING OPTIMIZED BUBBLE SORT ALGORITHM" << endl;
cout << "========================================" << endl;
int totalNumberOfSwaps = 0;
int totalNumberOfComparisons = 0;
for (int iteration = 0; iteration < arraySize - 1; iteration++)
{
bool hasSwapped = false;
cout << ">>> ITERATION " << (iteration + 1) << " <<<" << endl;
for (int currentIndex = 0; currentIndex < arraySize - iteration - 1; currentIndex++)
{
totalNumberOfComparisons++;
if (dataArray[currentIndex] > dataArray[currentIndex + 1]) {
swapElements(dataArray, currentIndex, currentIndex + 1);
hasSwapped = true;
totalNumberOfSwaps++;
}
}
// Early termination if no swaps occurred
if (!hasSwapped) {
cout << "No swaps in this iteration - array is already sorted!" << endl;
break;
}
cout << "Array after iteration " << (iteration + 1) << ": ";
for(int displayIndex = 0; displayIndex < arraySize; displayIndex++) {
cout << dataArray[displayIndex] << " ";
}
cout << endl << "--------------------------------" << endl;
}
cout << "Total comparisons: " << totalNumberOfComparisons << endl;
cout << "Total swaps: " << totalNumberOfSwaps << endl;
}
Características do Algoritmo
Complexidade de Tempo
- Melhor caso: O(n) - Array já ordenado (com otimização)
- Caso médio: O(n²) - Comportamento típico
- Pior caso: O(n²) - Array ordenado inversamente
Complexidade de Espaço
- O(1) - Algoritmo in-place, usa apenas memória constante adicional
Propriedades Importantes
| Propriedade | Valor |
|---|---|
| Estável | ✅ Sim |
| In-place | ✅ Sim |
| Adaptivo | ✅ Sim (com otimização) |
| Comparações | O(n²) |
| Trocas | O(n²) |
Por que o Bubble Sort É Estável?
O que significa "Estabilidade" em algoritmos de ordenação?
Um algoritmo de ordenação é estável quando mantém a ordem relativa dos elementos que possuem valores iguais. Ou seja, se dois elementos têm o mesmo valor, aquele que aparece primeiro no array original deve aparecer primeiro no array ordenado.
Exemplo Prático de Estabilidade
Considere um array de cartas onde cada carta tem um valor e um naipe:
Array inicial: [5♠, 3♦, 5♥, 2♣, 3♠]
Vamos ordenar por valor numérico apenas, ignorando o naipe:
✅ Bubble Sort (estável):
[2♣, 3♦, 3♠, 5♠, 5♥]
- Note que
3♦vem antes de3♠(mantém ordem original) - E
5♠vem antes de5♥(mantém ordem original)
Por que o Bubble Sort mantém a estabilidade?
O Bubble Sort mantém a estabilidade porque:
- Compara apenas elementos adjacentes
- Só troca elementos se o da esquerda for MAIOR que o da direita
- Nunca troca elementos iguais
Demonstração com números simples:
Array: [4, 2a, 2b, 1] (onde 2a e 2b têm o mesmo valor, mas origens diferentes)
Iteração 1:
- Compara 4 e 2a:
4 > 2a→ Troca:[2a, 4, 2b, 1] - Compara 4 e 2b:
4 > 2b→ Troca:[2a, 2b, 4, 1] - Compara 4 e 1:
4 > 1→ Troca:[2a, 2b, 1, 4]
Iteração 2:
- Compara 2a e 2b:
2a == 2b→ Sem troca (preserva ordem!) - Compara 2b e 1:
2b > 1→ Troca:[2a, 1, 2b, 4]
Iteração 3:
- Compara 2a e 1:
2a > 1→ Troca:[1, 2a, 2b, 4]
Resultado final: [1, 2a, 2b, 4] ✅ Ordem original mantida!
Exemplo Prático com Dados Reais
struct Pessoa {
string nome;
int idade;
int numeroChegada; // Para identificar ordem original
};
// Array inicial (ordenado por chegada):
// 1. João, 25 anos
// 2. Maria, 30 anos
// 3. Pedro, 25 anos
// 4. Ana, 20 anos
// Após Bubble Sort por idade:
// 1. Ana, 20 anos
// 2. João, 25 anos <- João mantém prioridade sobre Pedro
// 3. Pedro, 25 anos <- Pedro vem depois (ordem original preservada)
// 4. Maria, 30 anos
Importância da Estabilidade
A estabilidade é crucial quando:
- Ordenação múltipla: Primeiro por um campo, depois por outro
- Preservação de contexto: Manter informações sobre ordem original
- Interfaces de usuário: Comportamento previsível para o usuário
- Dados com metadados: Timestamps, IDs, etc.
Comparação com Algoritmos Instáveis
| Algoritmo | Estável? | Motivo |
|---|---|---|
| Bubble Sort | ✅ Sim | Só troca adjacentes se forem diferentes |
| Selection Sort | ❌ Não | Troca elementos distantes |
| Insertion Sort | ✅ Sim | Insere mantendo ordem |
| Quick Sort | ❌ Não | Particionamento pode alterar ordem |
| Merge Sort | ✅ Sim | Merge preserva ordem quando iguais |
Implementação que Garante Estabilidade
void stableBubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
// CRUCIAL: usar > e não >=
if (arr[j] > arr[j + 1]) { // Não troca elementos iguais!
swap(arr[j], arr[j + 1]);
}
}
}
}
🔑 Ponto-chave: Use
>(maior que) e nunca>=(maior ou igual) na condição de troca para manter a estabilidade!
Vantagens vs. Disvantagens
Vantagens
- ✅ Simples de implementar e entender
- ✅ Estável: Mantém a ordem relativa de elementos iguais
- ✅ In-place: Não requer memória adicional
- ✅ Adaptivo: Com otimização pode detectar arrays já ordenados
- ✅ Funciona bem com arrays pequenos
- ✅ Detecta facilmente se o array já está ordenado
Desvantagens
- ❌ Complexidade O(n²): Ineficiente para arrays grandes
- ❌ Muitas trocas: Pode fazer até O(n²) trocas no pior caso
- ❌ Lento na prática: Mesmo entre algoritmos O(n²)
- ❌ Não recomendado para dados em produção
- ❌ Elementos pequenos "borbulham" lentamente para o início
Quando Usar?
O Bubble Sort é adequado quando:
- Arrays muito pequenos (< 10 elementos)
- Estabilidade é crucial (manter ordem relativa de elementos iguais)
- Detecção de ordenação é importante (pode parar cedo se já ordenado)
- Fins educacionais (aprender conceitos de ordenação)
- Simplicidade extrema é mais importante que eficiência
- Protótipos rápidos onde performance não é crítica
Comparação com Outros Algoritmos
| Algoritmo | Melhor Caso | Caso Médio | Pior Caso | Estável | Trocas |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | ✅ | O(n²) |
| Selection Sort | O(n²) | O(n²) | O(n²) | ❌ | O(n) |
| Insertion Sort | O(n) | O(n²) | O(n²) | ✅ | O(n²) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | ✅ | - |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | ❌ | O(n log n) |
Variações do Bubble Sort
1. Bubble Sort Otimizado (com Flag)
Adiciona uma flag para detectar quando o array já está ordenado e para antecipadamente.
void optimizedBubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool hasSwapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
hasSwapped = true;
}
}
// Se não houve trocas, array está ordenado
if (!hasSwapped) {
break;
}
}
}
2. Cocktail Sort (Bubble Sort Bidirecional)
Funciona em ambas as direções alternadamente, melhorando a performance em alguns casos.
void cocktailSort(int arr[], int n) {
bool hasSwapped = true;
int start = 0;
int end = n - 1;
while (hasSwapped) {
hasSwapped = false;
// Esquerda para direita
for (int i = start; i < end; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
hasSwapped = true;
}
}
end--;
if (!hasSwapped) break;
// Direita para esquerda
for (int i = end; i > start; i--) {
if (arr[i] < arr[i - 1]) {
swap(arr[i], arr[i - 1]);
hasSwapped = true;
}
}
start++;
}
}
3. Bubble Sort Recursivo
Implementação recursiva que "borbulha" o maior elemento e ordena recursivamente o restante.
void recursiveBubbleSort(int arr[], int n) {
// Caso base
if (n == 1) return;
// Uma passada para colocar o maior elemento no final
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
}
}
// Chama recursivamente para os primeiros n-1 elementos
recursiveBubbleSort(arr, n - 1);
}
4. Odd-Even Sort (Brick Sort)
Variação que compara elementos em posições ímpares/pares alternadamente.
void oddEvenSort(int arr[], int n) {
bool isSorted = false;
while (!isSorted) {
isSorted = true;
// Compara elementos em posições ímpares
for (int i = 1; i <= n - 2; i += 2) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
isSorted = false;
}
}
// Compara elementos em posições pares
for (int i = 0; i <= n - 2; i += 2) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
isSorted = false;
}
}
}
}
Exercícios Práticos
Exercício 1: Implementação Básica
Implemente o Bubble Sort para ordenar um array de strings por ordem alfabética.
💡 Solução do Exercício 1
#include
#include
using namespace std;
// Função para trocar duas strings
void swapStrings(string arr[], int pos1, int pos2) {
cout << " -> Trocando \"" << arr[pos1] << "\" com \"" << arr[pos2] << "\"" << endl;
string temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
}
// Bubble Sort para strings
void bubbleSortStrings(string arr[], int size) {
cout << "Ordenando strings por ordem alfabética usando Bubble Sort:" << endl;
for (int i = 0; i < size - 1; i++) {
cout << "\n>>> ITERAÇÃO " << (i + 1) << " <<<" << endl;
bool hasSwapped = false;
for (int j = 0; j < size - i - 1; j++) {
cout << "Comparando \"" << arr[j] << "\" com \"" << arr[j + 1] << "\"";
if (arr[j] > arr[j + 1]) {
cout << " -> \"" << arr[j] << "\" > \"" << arr[j + 1] << "\", precisa trocar!" << endl;
swapStrings(arr, j, j + 1);
hasSwapped = true;
} else {
cout << " -> \"" << arr[j] << "\" <= \"" << arr[j + 1] << "\", sem troca" << endl;
}
}
cout << "Array após iteração " << (i + 1) << ": ";
for (int k = 0; k < size; k++) {
if (k >= size - i - 1) {
cout << "[\"" << arr[k] << "\"] ";
} else {
cout << "\"" << arr[k] << "\" ";
}
}
cout << endl;
if (!hasSwapped) {
cout << "Nenhuma troca realizada - array já está ordenado!" << endl;
break;
}
}
}
int main() {
const int SIZE = 6;
string nomes[SIZE] = {"Maria", "João", "Ana", "Pedro", "Carlos", "Beatriz"};
cout << "Array inicial: ";
for (int i = 0; i < SIZE; i++) {
cout << "\"" << nomes[i] << "\" ";
}
cout << endl << endl;
bubbleSortStrings(nomes, SIZE);
cout << "\n========================================" << endl;
cout << "RESULTADO FINAL:" << endl;
cout << "Array ordenado: ";
for (int i = 0; i < SIZE; i++) {
cout << "\"" << nomes[i] << "\" ";
}
cout << endl;
cout << "========================================" << endl;
return 0;
}
Exercício 2: Bubble Sort com Contador de Operações
Modifique o algoritmo Bubble Sort para contar e exibir o número total de comparações e trocas realizadas.
💡 Solução do Exercício 2
#include
using namespace std;
struct BubbleSortStats {
int comparisons;
int swaps;
int iterations;
};
void bubbleSortWithStats(int arr[], int size, BubbleSortStats& stats) {
stats.comparisons = 0;
stats.swaps = 0;
stats.iterations = 0;
cout << "Bubble Sort com estatísticas detalhadas:" << endl;
for (int i = 0; i < size - 1; i++) {
stats.iterations++;
cout << "\n>>> ITERAÇÃO " << stats.iterations << " <<<" << endl;
bool hasSwapped = false;
for (int j = 0; j < size - i - 1; j++) {
stats.comparisons++;
cout << "Comparação " << stats.comparisons << ": " << arr[j] << " vs " << arr[j + 1];
if (arr[j] > arr[j + 1]) {
// Realizar troca
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
stats.swaps++;
hasSwapped = true;
cout << " -> Troca " << stats.swaps << " realizada!" << endl;
} else {
cout << " -> Sem troca necessária" << endl;
}
}
cout << "Array após iteração " << stats.iterations << ": ";
for (int k = 0; k < size; k++) {
cout << arr[k] << " ";
}
cout << endl;
if (!hasSwapped) {
cout << "Otimização: Array já ordenado, parando antecipadamente!" << endl;
break;
}
}
}
int main() {
int numeros[] = {64, 34, 25, 12, 22, 11, 90};
int tamanho = sizeof(numeros) / sizeof(numeros[0]);
BubbleSortStats estatisticas;
cout << "Array inicial: ";
for (int i = 0; i < tamanho; i++) {
cout << numeros[i] << " ";
}
cout << endl;
bubbleSortWithStats(numeros, tamanho, estatisticas);
cout << "\n========================================" << endl;
cout << "ESTATÍSTICAS FINAIS:" << endl;
cout << "Iterações realizadas: " << estatisticas.iterations << endl;
cout << "Total de comparações: " << estatisticas.comparisons << endl;
cout << "Total de trocas: " << estatisticas.swaps << endl;
cout << "Array final: ";
for (int i = 0; i < tamanho; i++) {
cout << numeros[i] << " ";
}
cout << endl;
cout << "========================================" << endl;
return 0;
}
Exercício 3: Bubble Sort Bidirecional (Cocktail Sort)
Implemente uma variação do Bubble Sort que funciona nas duas direções.
💡 Solução do Exercício 3
#include
using namespace std;
void cocktailSort(int arr[], int size) {
cout << "Implementando Cocktail Sort (Bubble Sort Bidirecional):" << endl;
bool hasSwapped = true;
int start = 0;
int end = size - 1;
int iteration = 0;
while (hasSwapped) {
iteration++;
hasSwapped = false;
cout << "\n>>> ITERAÇÃO " << iteration << " - DIREÇÃO →" << endl;
// Passada da esquerda para direita
for (int i = start; i < end; i++) {
cout << "Comparando " << arr[i] << " com " << arr[i + 1];
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
hasSwapped = true;
cout << " -> Trocado!" << endl;
} else {
cout << " -> Sem troca" << endl;
}
}
if (!hasSwapped) {
break;
}
end--;
cout << "\n>>> ITERAÇÃO " << iteration << " - DIREÇÃO ←" << endl;
// Passada da direita para esquerda
for (int i = end; i > start; i--) {
cout << "Comparando " << arr[i] << " com " << arr[i - 1];
if (arr[i] < arr[i - 1]) {
swap(arr[i], arr[i - 1]);
hasSwapped = true;
cout << " -> Trocado!" << endl;
} else {
cout << " -> Sem troca" << endl;
}
}
start++;
cout << "Array após iteração " << iteration << ": ";
for (int j = 0; j < size; j++) {
cout << arr[j] << " ";
}
cout << endl;
}
}
int main() {
int numeros[] = {5, 1, 4, 2, 8, 0, 2};
int tamanho = sizeof(numeros) / sizeof(numeros[0]);
cout << "Array inicial: ";
for (int i = 0; i < tamanho; i++) {
cout << numeros[i] << " ";
}
cout << endl;
cocktailSort(numeros, tamanho);
cout << "\nArray final ordenado: ";
for (int i = 0; i < tamanho; i++) {
cout << numeros[i] << " ";
}
cout << endl;
return 0;
}
Exercício 4: Análise de Performance
Compare o desempenho do Bubble Sort com e sem otimização de parada antecipada.
🤔 Desafio Extra
Implemente uma versão do Bubble Sort que:
- Conta operações (comparações e trocas)
- Para automaticamente quando detecta que está ordenado
- Mostra estatísticas detalhadas no final
- Funciona com diferentes tipos de dados (int, float, string)
🏆 Solução do Desafio Extra
#include <iostream>
#include <string>
#include <vector>
#include <chrono>
#include <iomanip>
using namespace std;
using namespace std::chrono;
// Estrutura para armazenar estatísticas de ordenação
struct SortingStats {
int comparisons = 0;
int swaps = 0;
int iterations = 0;
double timeElapsed = 0.0;
bool optimizedExit = false;
};
// Template para Bubble Sort genérico com estatísticas
template<typename T>
void advancedBubbleSort(T arr[], int size, SortingStats& stats) {
auto start = high_resolution_clock::now();
cout << "\n========================================" << endl;
cout << "ADVANCED BUBBLE SORT WITH STATISTICS" << endl;
cout << "========================================" << endl;
stats = {0, 0, 0, 0.0, false}; // Reset statistics
cout << "Array inicial: ";
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl << endl;
bool hasSwapped = true;
while (hasSwapped && stats.iterations < size - 1) {
hasSwapped = false;
stats.iterations++;
cout << ">>> ITERAÇÃO " << stats.iterations << " <<<" << endl;
for (int i = 0; i < size - stats.iterations; i++) {
stats.comparisons++;
cout << "Comparação " << stats.comparisons << ": "
<< arr[i] << " vs " << arr[i + 1];
if (arr[i] > arr[i + 1]) {
// Realizar troca
T temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
stats.swaps++;
hasSwapped = true;
cout << " -> Troca " << stats.swaps << " realizada!" << endl;
} else {
cout << " -> Sem troca necessária" << endl;
}
}
cout << "Estado do array: ";
for (int i = 0; i < size; i++) {
if (i >= size - stats.iterations) {
cout << "[" << arr[i] << "] ";
} else {
cout << arr[i] << " ";
}
}
cout << endl;
if (!hasSwapped) {
stats.optimizedExit = true;
cout << "🎯 OTIMIZAÇÃO: Array já ordenado! Parando antecipadamente." << endl;
}
cout << "--------------------------------" << endl;
}
auto end = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(end - start);
stats.timeElapsed = duration.count() / 1000.0; // Convert to milliseconds
cout << "\n========================================" << endl;
cout << "ESTATÍSTICAS DETALHADAS" << endl;
cout << "========================================" << endl;
cout << "Elementos no array: " << size << endl;
cout << "Iterações realizadas: " << stats.iterations << endl;
cout << "Total de comparações: " << stats.comparisons << endl;
cout << "Total de trocas: " << stats.swaps << endl;
cout << "Tempo de execução: " << fixed << setprecision(3)
<< stats.timeElapsed << " ms" << endl;
cout << "Otimização ativada: " << (stats.optimizedExit ? "✅ Sim" : "❌ Não") << endl;
cout << "Eficiência: " << fixed << setprecision(2)
<< ((double)stats.swaps / stats.comparisons * 100) << "% das comparações resultaram em trocas" << endl;
cout << "\nArray final ordenado: ";
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
cout << "========================================" << endl;
}
// Função para testar com diferentes tipos de dados
void testWithIntegers() {
cout << "\n🔢 TESTE COM NÚMEROS INTEIROS" << endl;
int numeros[] = {64, 34, 25, 12, 22, 11, 90};
int tamanho = sizeof(numeros) / sizeof(numeros[0]);
SortingStats stats;
advancedBubbleSort(numeros, tamanho, stats);
}
void testWithFloats() {
cout << "\n🔢 TESTE COM NÚMEROS DECIMAIS" << endl;
float decimais[] = {3.14f, 2.71f, 1.41f, 1.73f, 0.57f};
int tamanho = sizeof(decimais) / sizeof(decimais[0]);
SortingStats stats;
advancedBubbleSort(decimais, tamanho, stats);
}
void testWithStrings() {
cout << "\n📝 TESTE COM STRINGS" << endl;
string nomes[] = {"Maria", "João", "Ana", "Pedro", "Carlos"};
int tamanho = sizeof(nomes) / sizeof(nomes[0]);
SortingStats stats;
advancedBubbleSort(nomes, tamanho, stats);
}
void testWithAlreadySorted() {
cout << "\n✅ TESTE COM ARRAY JÁ ORDENADO (Demonstração de Otimização)" << endl;
int ordenado[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int tamanho = sizeof(ordenado) / sizeof(ordenado[0]);
SortingStats stats;
advancedBubbleSort(ordenado, tamanho, stats);
}
void testWithReverseSorted() {
cout << "\n❌ TESTE COM ARRAY INVERSAMENTE ORDENADO (Pior Caso)" << endl;
int reverso[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
int tamanho = sizeof(reverso) / sizeof(reverso[0]);
SortingStats stats;
advancedBubbleSort(reverso, tamanho, stats);
}
// Função para comparar performance
void performanceComparison() {
cout << "\n📊 COMPARAÇÃO DE PERFORMANCE" << endl;
cout << "=============================" << endl;
// Teste com diferentes tamanhos
vector<int> sizes = {5, 10, 15};
for (int size : sizes) {
cout << "\n🔍 Testando com " << size << " elementos:" << endl;
// Criar array aleatório
int* arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = rand() % 100;
}
SortingStats stats;
advancedBubbleSort(arr, size, stats);
cout << "Resultado: " << stats.iterations << " iterações, "
<< stats.comparisons << " comparações, "
<< stats.swaps << " trocas em "
<< stats.timeElapsed << " ms" << endl;
delete[] arr;
}
}
int main() {
cout << "==================================================" << endl;
cout << "BUBBLE SORT AVANÇADO - DESAFIO EXTRA COMPLETO" << endl;
cout << "==================================================" << endl;
// Teste com diferentes tipos de dados
testWithIntegers();
testWithFloats();
testWithStrings();
// Testes especiais para demonstrar otimizações
testWithAlreadySorted();
testWithReverseSorted();
// Comparação de performance
performanceComparison();
cout << "\n🎉 Todos os testes foram concluídos com sucesso!" << endl;
cout << "📚 Este exemplo demonstra:" << endl;
cout << " ✅ Contagem de operações" << endl;
cout << " ✅ Parada antecipada (otimização)" << endl;
cout << " ✅ Estatísticas detalhadas" << endl;
cout << " ✅ Suporte a diferentes tipos de dados" << endl;
cout << " ✅ Medição de tempo de execução" << endl;
cout << " ✅ Análise de eficiência" << endl;
return 0;
}
Explicação da Solução
Esta solução avançada implementa todos os requisitos do desafio:
1. Contagem de Operações
- Struct
SortingStatsarmazena comparações, trocas, iterações e tempo - Cada operação é contada e exibida em tempo real
2. Parada Antecipada
- Flag
hasSwappeddetecta quando não há mais trocas - Para automaticamente, economizando iterações desnecessárias
3. Estatísticas Detalhadas
- Número total de operações realizadas
- Tempo de execução em milissegundos
- Percentual de eficiência (trocas/comparações)
- Indicação se a otimização foi ativada
4. Suporte a Diferentes Tipos
- Template genérico funciona com
int,float,string - Testes demonstram funcionamento com cada tipo
5. Recursos Extras
- Visualização do processo de ordenação
- Testes com casos especiais (já ordenado, inverso)
- Comparação de performance com diferentes tamanhos
- Medição precisa de tempo de execução
Esta implementação é ideal para estudos avançados de algoritmos e análise de performance!
Conclusão
O Bubble Sort é um algoritmo fundamental para aprender os conceitos de ordenação devido à sua simplicidade conceitual e facilidade de implementação. Embora não seja eficiente para arrays grandes, é excelente para fins educacionais e situações específicas onde a estabilidade é crucial.
O algoritmo demonstra claramente os conceitos de:
- Comparação de elementos adjacentes
- Algoritmos estáveis vs. instáveis
- Otimizações algorítmicas (parada antecipada)
- Análise de complexidade no melhor e pior caso
- Trade-offs entre simplicidade e eficiência
Quando usar Bubble Sort:
- Arrays muito pequenos (< 10 elementos)
- Situações educacionais
- Quando a estabilidade é essencial
- Como base para entender algoritmos mais complexos
Top comments (2)
Que post massa, conteúdo muito bom!
Obrigado mano
Tenho outros conteúdos se quiser dar uma olhada, espero que tenha sido útil!