Nesta aula, demos início ao estudo de algoritmos de ordenação. Ordenar elementos é uma tarefa fundamental em computação, presente em diversas aplicações, desde a organização de listas até a otimização de buscas. Vimos três algoritmos clássicos: Bubble Sort, Selection Sort e Insertion Sort. Todos eles têm complexidade O(n²), mas possuem características que os tornam adequados para diferentes cenários. Abaixo detalhamos cada um.

O que são algoritmos de ordenação?

Algoritmos de ordenação são métodos para reorganizar os elementos de uma sequência (como uma lista ou array) em uma ordem específica, geralmente crescente ou decrescente. A escolha do algoritmo impacta diretamente o desempenho, especialmente quando lidamos com grandes volumes de dados. Nesta aula, focamos em algoritmos simples, didáticos, que servem de base para compreender conceitos como complexidade de tempo e espaço.

Bubble Sort

O Bubble Sort funciona percorrendo repetidamente a lista, comparando elementos adjacentes e trocando-os se estiverem na ordem errada. Esse processo é repetido até que a lista esteja ordenada. O nome "bubble" (bolha) vem do fato de que os maiores elementos "flutuam" para o final como bolhas.

Complexidade: no pior caso (lista reversa), O(n²). No melhor caso (lista já ordenada), O(n) se implementado com uma flag de troca.

def bubble_sort(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

Selection Sort

O Selection Sort divide a lista em duas partes: a parte ordenada (inicialmente vazia) e a parte não ordenada. A cada iteração, seleciona o menor elemento da parte não ordenada e o coloca no final da parte ordenada. É simples, mas ineficiente para listas grandes.

Complexidade: O(n²) em qualquer caso, pois sempre percorre toda a parte não ordenada.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Insertion Sort

O Insertion Sort constrói a saída ordenada um elemento de cada vez. Ele percorre a lista da esquerda para a direita e insere cada elemento na posição correta entre os elementos já ordenados. É semelhante à forma como ordenamos cartas de baralho na mão.

Complexidade: pior caso O(n²), melhor caso O(n) (lista já ordenada). Muito eficiente para listas pequenas ou parcialmente ordenadas.

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

Comparação

A tabela abaixo resume as principais características que vimos em aula:

Algoritmo Melhor caso Pior caso Estável Memória extra
Bubble Sort O(n) O(n²) Sim O(1)
Selection Sort O(n²) O(n²) Não O(1)
Insertion Sort O(n) O(n²) Sim O(1)

O Bubble Sort, embora ineficiente, é útil para entender trocas. O Selection Sort minimiza o número de trocas, mas não é estável. O Insertion Sort é geralmente o mais rápido entre os três para arranjos pequenos e é estável.

Implementação completa em Python

Abaixo está um exemplo de uso dos três algoritmos:

arr = [64, 34, 25, 12, 22, 11, 90]
print("Original:", arr)
print("Bubble:", bubble_sort(arr.copy()))
print("Selection:", selection_sort(arr.copy()))
print("Insertion:", insertion_sort(arr.copy()))

Conclusão

Os algoritmos de ordenação são a base para entender complexidade e estrutura de dados. Apesar de existirem algoritmos mais rápidos como Merge Sort e Quick Sort, os três vistos hoje são importantes para o aprendizado. Na próxima aula, veremos algoritmos recursivos e notação assintótica mais aprofundada.

Perguntas Frequentes

Qual destes algoritmos é o melhor?
Depende do cenário. Para listas muito pequenas (até cerca de 50 elementos), Insertion Sort costuma ser o mais rápido. Para listas grandes, os O(n²) são inadequados; preferimos Merge Sort ou Quick Sort.

O que significa "estável"?
Um algoritmo de ordenação é estável se mantém a ordem relativa de elementos iguais. Isso é importante em ordenações secundárias.

Por que estudar algoritmos lentos?
Eles são didáticos e ajudam a entender conceitos fundamentais de análise de algoritmos. Além disso, aparecem em problemas específicos onde a lista já está parcialmente ordenada.