- Um algoritmo simples e estável que ordena comparando e trocando elementos adjacentes, ideal para aprender os fundamentos.
- Sua complexidade é O(n^2), portanto é ineficiente em conjuntos grandes e realiza muitas comparações desnecessárias.
- Foi demonstrada a sua implementação em C, Java e Python; existem alternativas mais eficientes, como o quicksort e o mergesort, para conjuntos de dados maiores.
O algoritmo de classificação por bolhas é um dos algoritmos mais simples e básicos usados para classificar elementos em uma lista. Sua simplicidade o torna uma excelente escolha para entender os conceitos fundamentais dos algoritmos de classificação. Este algoritmo é comumente usado em aplicações e programas onde o número de elementos a serem classificados é pequeno.
Neste artigo, vamos nos concentrar na implementação do algoritmo de ordenação por bolha em duas linguagens de programação populares: C e Java. Exploraremos os passos necessários para implementar esse algoritmo em cada uma dessas linguagens, analisando o código-fonte e fornecendo explicações detalhadas.
Algoritmo Bubble Sort em C e Java
O algoritmo de classificação por bolhas, como o nome sugere, funciona comparando pares de elementos adjacentes em uma lista e realizando trocas se eles estiverem na ordem errada. Esse processo é repetido até que a lista esteja completamente classificada.
Como o algoritmo de classificação por bolhas funciona em C e Java?
O algoritmo de classificação por bolhas segue uma abordagem simples, mas eficaz, para classificar elementos. A operação geral do algoritmo é mostrada abaixo:
- Começamos com uma lista não ordenada de itens.
- Iteramos pela lista, comparando cada par de elementos adjacentes.
- Se os elementos estiverem na ordem errada, nós os trocamos.
- Continuamos iterando na lista até que ela esteja completamente classificada.
- O processo de iteração é repetido quantas vezes forem necessárias até que não sejam feitas mais trocas em uma passagem completa.
Implementação do algoritmo bubble sort em C
A seguir, apresentamos a implementação do algoritmo de ordenação por bolha na linguagem C :
#include <stdio.h>
void bubbleSort(int array[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
int main() {
int array[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(array) / sizeof(array[0]);
bubbleSort(array, size);
printf("Array ordenado: ");
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
return 0;
}
Neste código de algoritmo de bolha, definimos uma função chamada bubbleSort que recebe um array e seu tamanho como parâmetros. A função executa o algoritmo de classificação de bolhas usando dois loops for. O primeiro loop for itera sobre os elementos da matriz e o segundo loop for faça as comparações e trocas necessárias.
Por fim, na função main, criamos uma matriz de exemplo e calculamos seu tamanho. Então chamamos a função bubbleSort passando o array e seu tamanho como argumentos. Por fim, imprimimos o array ordenado na tela.
Implementação do algoritmo bubble sort em Java
Abaixo apresentamos a implementação do algoritmo bubble sort na linguagem Java:
import java.util.Arrays;
public class BubbleSort {
public static void bubbleSort(int[] array) {
int size = array.length;
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] array = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(array);
System.out.println("Array ordenado: " + Arrays.toString(array));
}
}
Neste código, definimos uma classe chamada BubbleSort. Dentro desta classe, declaramos um método estático chamado bubbleSort que recebe um array como parâmetro. O método bubbleSort executa o algoritmo de classificação de bolhas usando dois loops for, assim como na implementação C.
no método main, criamos um array de exemplo e chamamos o método bubbleSort passando o array como argumento. Por fim, usamos Arrays.toString(array) para imprimir a matriz classificada no console.
Implementando o algoritmo bubble sort em Python
O equivalente ao algoritmo de classificação por bolhas do Python:
def bubble_sort(array):
size = len(array)
for i in range(size - 1):
for j in range(size - i - 1):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
array = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(array)
print("Array ordenado:", array)
Vantagens do algoritmo de classificação por bolhas
O algoritmo de classificação por bolhas tem algumas vantagens, como:
- Facilidade: O algoritmo de classificação por bolhas é fácil de entender e implementar. Não requer conhecimentos complexos e é adequado para iniciantes em programação.
- Baixa complexidade de código:O código necessário para implementar o algoritmo de classificação por bolhas é relativamente curto e conciso. Isso o torna uma opção rápida para classificar um pequeno número de itens.
Desvantagens do algoritmo de classificação de bolhas
Apesar de sua simplicidade, o algoritmo de classificação por bolhas também tem algumas desvantagens:
- Ineficiência em grandes conjuntos de dados: O algoritmo de classificação por bolhas não é eficiente em termos de tempo de execução ao lidar com grandes conjuntos de dados. Sua complexidade de tempo é O(n^2), o que significa que o tempo de execução aumenta rapidamente à medida que o tamanho do conjunto de dados aumenta.
- Número de comparações: O algoritmo de classificação por bolhas realiza um grande número de comparações, mesmo quando a matriz já está classificada. Isso pode levar à perda desnecessária de desempenho e recursos.
Alternativas ao algoritmo de classificação por bolhas
À medida que os conjuntos de dados se tornam maiores e mais complexos, é importante considerar alternativas mais eficientes ao algoritmo de classificação por bolhas. Algumas das alternativas populares incluem:
- Algoritmo de ordenação por inserção: Este algoritmo divide a lista em uma parte ordenada e uma parte não ordenada, e insere cada elemento da parte não ordenada na posição correta dentro da parte ordenada. Ele tem uma complexidade de tempo de O(n^2) no pior caso, mas é mais eficiente que o algoritmo de classificação por bolhas na maioria dos casos.
- Algoritmo de classificação por seleção: Este algoritmo divide a lista em uma parte ordenada e uma parte não ordenada, e seleciona repetidamente o menor elemento da parte não ordenada e o coloca no final da parte ordenada. Ele tem uma complexidade de tempo de O(n^2) no pior caso, mas também é mais eficiente que o algoritmo de classificação por bolhas na maioria dos casos.
Perguntas frequentes sobre o algoritmo de bolhas
1. Qual é a complexidade de tempo do algoritmo de classificação por bolhas?
O algoritmo de classificação por bolhas tem uma complexidade de tempo de O(n^2), onde “n” é o número de elementos a serem classificados. Isso significa que o tempo de execução do algoritmo aumenta quadraticamente à medida que o tamanho da lista aumenta.
2. Quando é apropriado usar o algoritmo de classificação por bolhas?
O algoritmo de classificação por bolhas é adequado quando a lista de elementos a serem classificados é pequena. Devido à sua complexidade de tempo, não é recomendado para uso em grandes conjuntos de dados, pois há algoritmos mais eficientes disponíveis.
3. O algoritmo de classificação por bolhas é estável?
Sim, o algoritmo de classificação por bolhas é um algoritmo de classificação estável. Isso significa que ele mantém a ordem relativa dos elementos com chaves iguais durante o processo de classificação.
4. Qual é a melhor alternativa ao algoritmo bubble sort?
A escolha da melhor alternativa ao algoritmo de ordenação por bolha depende do contexto e dos requisitos específicos do problema. No entanto, alguns algoritmos mais eficientes, como o quicksort e o mergesort , são amplamente utilizados devido à sua menor complexidade temporal.
5. O algoritmo de classificação por bolhas pode ser melhorado?
Sim, existem variantes e otimizações do algoritmo de classificação por bolhas, como “classificação por bolhas bidirecional” e “classificação por bolhas aprimorada”. Essas otimizações reduzem o número de comparações e o número de iterações necessárias para classificar uma lista.
6. Onde posso encontrar mais informações sobre algoritmos de classificação?
Você pode encontrar mais informações sobre algoritmos de classificação em fontes confiáveis, como a Wikipédia. Aqui estão alguns links úteis:
Conclusão
Neste artigo, exploramos o algoritmo de classificação por bolhas nas linguagens de programação C e Java. Aprendemos como esse algoritmo funciona passo a passo e vimos sua implementação prática em ambas as linguagens. Também discutimos as vantagens e desvantagens do algoritmo de classificação por bolhas e exploramos alternativas mais eficientes.
Embora o algoritmo de classificação por bolhas seja simples e fácil de implementar, é importante considerar sua eficiência em conjuntos de dados maiores. Nesses casos, é aconselhável considerar algoritmos de classificação mais eficientes, como classificação por inserção ou classificação por seleção.
Esperamos que este artigo tenha lhe dado uma compreensão sólida do algoritmo de classificação por bolhas.