O que é e como funciona o BubbleSort?

O que é BubbleSort?

O Bubble sort é um algoritmo simples de ordenação que recebe como entrada uma lista de elementos e produz uma lista ordenada de acordo com um critério. É um algoritmo popular, mas menos eficiente em relação a outros algoritmos de ordenação.

Exemplo simples

Imagine que você tem uma sequência de números, como 5, 1, 9, 3, e deseja ordená-los em ordem crescente. O Bubble sort pode ajudar nessa tarefa, reorganizando os números até que estejam na ordem correta.

Exemplo de implementação em C#

Confira esse exemplo na linguagem de programação C#.

using System;

class Program {
    static void Main(string[] args) {
        int[] numeros = {5, 1, 9, 3}; // Array de números a ser ordenado
        int tamanho = numeros.Length;

        // Loop principal do Bubble Sort
        for (int i = 0; i < tamanho - 1; i++) {
            for (int j = 0; j < tamanho - i - 1; j++) {
                if (numeros[j] > numeros[j+1]) {
                    // Troca os elementos de posição
                    int temp = numeros[j];
                    numeros[j] = numeros[j+1];
                    numeros[j+1] = temp;
                }
            }
        }

        // Imprime o array ordenado
        Console.WriteLine("Array ordenado:");
        for (int i = 0; i < tamanho; i++) {
            Console.Write(numeros[i] + " ");
        }
    }
}

// Fonte: ChatGPT

Exemplo de implementação em Python

Confira esse exemplo na linguagem de programação Python.

numeros = [5, 1, 9, 3] # Lista de números a ser ordenado
tamanho = len(numeros)

# Loop principal do Bubble Sort
for i in range(tamanho - 1):
    for j in range(tamanho - i - 1):
        if numeros[j] > numeros[j+1]:
            # Troca os elementos de posição
            numeros[j], numeros[j+1] = numeros[j+1], numeros[j]

# Imprime a lista ordenada
print("Lista ordenada:")
for i in range(tamanho):
    print(numeros[i], end=" ")

# Fonte: ChatGPT

Exemplo de implementação em Java

Confira esse exemplo na linguagem de programação Java.

public class BubbleSort {
    public static void main(String[] args) {
        int[] numeros = {5, 1, 9, 3}; // Array de números a ser ordenado
        int tamanho = numeros.length;

        // Loop principal do Bubble Sort
        for (int i = 0; i < tamanho - 1; i++) {
            for (int j = 0; j < tamanho - i - 1; j++) {
                if (numeros[j] > numeros[j+1]) {
                    // Troca os elementos de posição
                    int temp = numeros[j];
                    numeros[j] = numeros[j+1];
                    numeros[j+1] = temp;
                }
            }
        }

        // Imprime o array ordenado
        System.out.println("Array ordenado:");
        for (int i = 0; i < tamanho; i++) {
            System.out.print(numeros[i] + " ");
        }
    }
}

// Fonte: ChatGPT

Como funciona o BubbleSort

Funcionamento básico

O funcionamento do Bubble sort é baseado na comparação dos elementos da lista e na troca de posição dos mesmos quando necessário para atingir a ordenação pretendida. Ele atua localmente, ou seja, pode alterar a própria lista de entrada.

Passo a passo do algoritmo

1. Percorra a lista da esquerda para a direita.
2. Compare cada elemento com o elemento adjacente à sua direita.
3. Se o elemento à esquerda for maior que o elemento à direita, troque-os de posição.
4. Repita os passos 1a 3 até que a lista esteja ordenada.

Analisando a eficiência do BubbleSort

Comparação de elementos

O Bubble sort compara cada elemento com o elemento adjacente, o que aumenta o número de comparações à medida que o tamanho da lista aumenta.

Troca de posição dos elementos

Sempre que o Bubble sort encontra elementos fora de ordem, ele troca suas posições. Isso significa que o algoritmo pode realizar várias trocas para cada par de elementos, aumentando ainda mais o tempo de execução.

Complexidade do algoritmo

A complexidade do Bubble sort é O(n^2) no pior caso e no caso médio, onde n é o número de elementos na lista. No entanto, no melhor caso, quando a lista já está ordenada, a complexidade é O(n).

Casos de melhor e pior desempenho

O melhor caso ocorre quando a lista já está ordenada, e o Bubble sort apenas percorre a lista uma vez para verificar isso. O pior caso ocorre quando a lista está ordenada na ordem inversa, exigindo que o algoritmo realize várias trocas e percorra a lista várias vezes.

Alternativas ao BubbleSort

Outros algoritmos de ordenação

Embora o Bubble sort seja simples e fácil de entender, existem algoritmos de ordenação mais eficientes disponíveis, como o QuickSort, o MergeSort e o HeapSort. Esses algoritmos geralmente têm melhor desempenho e são preferidos para listas maiores.

Comparação entre algoritmos

Comparando o Bubble sort com algoritmos como o QuickSort e o MergeSort, o Bubble sort é geralmente mais lento e menos eficiente. Porém, em casos específicos, como listas pequenas ou quase ordenadas, o Bubble sort pode ser uma opção adequada.

Bubble Sort: uma escolha eficaz para pequenas listas

O Bubble sort é um algoritmo de ordenação simples e popular, mas menos eficiente em comparação com outras opções disponíveis. Ele funciona comparando e trocando elementos adjacentes até que a lista esteja ordenada. Embora não seja a melhor escolha para listas grandes, ele pode ser útil em casos específicos e é fácil de entender e implementar.

Esse conteúdo é parte do material disponibilizado para os participantes do meu grupo de estudos de Algoritmos e Estruturas de Dados. Você quer participar desse grupo? Clique aqui e veja como funciona.