Nesta aula vamos explorar dois algoritmos de ordenação clássicos: Bubble Sort e Insertion Sort. Ambos são considerados algoritmos simples e didáticos, sendo frequentemente os primeiros que aprendemos em um curso de ciências da computação. Embora não sejam os mais eficientes para grandes conjuntos de dados, eles nos ajudam a entender conceitos fundamentais como complexidade de tempo, invariantes de laço e a importância de escolher a estrutura de dados adequada.

A ordenação é uma operação essencial em computação. Ordenar dados permite que buscas sejam realizadas de forma mais eficiente (como a busca binária) e facilita a análise e apresentação das informações. Vamos implementar cada um em Python e analisar seu desempenho.

Bubble Sort

O Bubble Sort funciona comparando elementos adjacentes e trocando‑os se estiverem na ordem errada. Esse processo se repete até que o array esteja ordenado. O nome “bolha” vem do fato de que os maiores elementos “flutuam” para o final do array a cada iteração.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Análise de complexidade: O Bubble Sort tem complexidade O(n²) no pior caso e O(n) no melhor caso (quando o array já está ordenado e utilizamos uma otimização com flag). O caso médio também é O(n²). Ele não é recomendado para grandes volumes de dados, mas é fácil de implementar e entender.

Otimização: podemos adicionar uma variável swapped para verificar se houve troca em uma passagem; se não houve, o array já está ordenado e podemos interromper.

def bubble_sort_otimizado(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

Insertion Sort

O Insertion Sort constrói o array ordenado um elemento por vez, inserindo cada novo elemento na posição correta entre os já ordenados. É semelhante à forma como organizamos cartas em uma mão.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Análise de complexidade: O Insertion Sort também tem complexidade O(n²) no pior caso (array invertido) e O(n) no melhor caso (array ordenado). Ele é mais eficiente que o Bubble Sort na prática, pois faz menos trocas e tem um desempenho melhor em listas quase ordenadas.

Comparação entre os algoritmos

Algoritmo Melhor Caso Pior Caso Estável In‑place
Bubble Sort O(n) O(n²) Sim Sim
Insertion Sort O(n) O(n²) Sim Sim

Ambos são estáveis (preservam a ordem de elementos iguais) e in‑place (não requerem memória extra significativa). O Insertion Sort é geralmente mais rápido que o Bubble Sort para arrays pequenos ou quase ordenados, enquanto o Bubble Sort pode ser útil apenas para fins educacionais.

Pontos‑chave

  • Bubble Sort: simples, O(n²), estável, in‑place, adequado para aprendizado.
  • Insertion Sort: eficiente para listas quase ordenadas, O(n²) pior caso, estável, in‑place.
  • Ambos são recomendados para pequenos conjuntos de dados ou como base para algoritmos mais avançados.
  • A escolha entre eles depende do cenário: Insertion Sort quase sempre supera Bubble Sort na prática.

Conclusão

Nesta aula vimos os conceitos fundamentais dos algoritmos Bubble Sort e Insertion Sort. Embora simples, eles formam a base para entendermos algoritmos mais avançados como Merge Sort e Quick Sort, que veremos em aulas futuras. Pratique implementando esses algoritmos em diferentes linguagens e testando com diferentes entradas.

Para continuar estudando, confira outras aulas na página de Posts do blog.

Faça você mesmo: tente modificar os códigos para contar o número de comparações e trocas, e compare o desempenho dos dois algoritmos.

Perguntas Frequentes

Qual a diferença entre Bubble Sort e Insertion Sort?

Ambos são algoritmos de ordenação O(n²), mas o Insertion Sort tende a ser mais rápido porque realiza menos trocas e aproveita melhor a ordenação parcial dos dados. O Bubble Sort troca elementos adjacentes repetidamente, o que pode ser ineficiente.

Quando usar Bubble Sort?

Basicamente em contextos educacionais ou quando a simplicidade do código é mais importante que a eficiência. Raramente é usado em produção.

O Insertion Sort é melhor que o Bubble Sort?

Sim, na maioria dos casos. Insertion Sort tem melhor desempenho prático, especialmente em listas pequenas ou quase ordenadas. Ambos são estáveis e in‑place, mas Insertion Sort é geralmente preferido.

Esses algoritmos são usados na prática?

O Insertion Sort é usado como parte de algoritmos híbridos (como no Timsort do Python) para ordenar pequenas partições. Já o Bubble Sort é raramente usado em produção, sendo mais uma ferramenta didática.