Hoje vamos estudar algoritmos de ordenação. Ordenar dados é uma tarefa essencial em computação. Vamos ver três algoritmos simples: Bubble Sort, Selection Sort e Insertion Sort. Implementaremos cada um em Python e analisaremos suas complexidades.

Bubble Sort

O Bubble Sort percorre a lista repetidamente, trocando elementos adjacentes que estão fora de ordem. A cada passagem, o maior elemento "flutua" para o final, como uma bolha.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        trocou = 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]
                trocou = True
        if not trocou:
            break
    return arr

Complexidade: melhor caso O(n) (lista já ordenada), pior e médio O(n²). É estável e in-place. A otimização com a flag trocou evita passagens desnecessárias.

Selection Sort

O Selection Sort seleciona o menor elemento da parte não ordenada e o coloca na posição correta. Ele realiza poucas trocas: no máximo n−1.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        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>

Complexidade: sempre O(n²) — mesmo se a lista estiver ordenada. Não é estável (a troca pode desrespeitar a ordem relativa de elementos iguais). É in-place.

Insertion Sort

O Insertion Sort constrói a lista ordenada inserindo cada elemento na posição correta, como ao ordenar cartas de baralho.

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>

Complexidade: melhor O(n), pior O(n²). É estável, in-place e adaptável: eficiente para listas pequenas ou quase ordenadas. Por isso é usado em algoritmos híbridos como o Timsort.

Comparação

A tabela a seguir resume as principais características:

Algoritmo Melhor Caso Pior Caso Caso Médio Estável Memória
Bubble Sort O(n) O(n²) O(n²) Sim O(1)
Selection Sort O(n²) O(n²) O(n²) Não O(1)
Insertion Sort O(n) O(n²) O(n²) Sim O(1)

Estabilidade

Um algoritmo de ordenação é estável quando mantém a ordem relativa de elementos com chaves iguais. Isso é importante em ordenações múltiplas. Dos três, Bubble Sort e Insertion Sort são estáveis; Selection Sort não é, pois a troca pode deslocar um elemento repetido para depois de outro igual.

Análise de Complexidade

A complexidade de tempo é determinada pelo número de comparações e trocas. Todos têm laços aninhados que resultam em O(n²) no pior caso. Insertion Sort e Bubble Sort (com otimização) podem atingir O(n) no melhor caso. Selection Sort não possui essa melhoria.

Aplicações Práticas

  • Bubble Sort: usado principalmente para fins didáticos. Raramente aplicado em produção.
  • Selection Sort: útil quando o custo de troca é muito elevado, pois realiza poucas trocas (O(n)).
  • Insertion Sort: muito eficiente para conjuntos pequenos (até ~50 elementos) ou quase ordenados. É o algoritmo base de ordenação em muitas linguagens para partições pequenas.

Exercícios Sugeridos

  1. Implemente cada algoritmo e teste com listas de diferentes tamanhos e ordenações.
  2. Compare o desempenho medindo o tempo de execução para listas de 1000, 5000 e 10000 elementos.
  3. Modifique o Selection Sort para torná-lo estável (dica: use inserção em vez de troca).
  4. Implemente uma versão recursiva do Bubble Sort.

Conclusão

Nesta aula vimos os fundamentos dos algoritmos de ordenação simples. Eles servem como base para entender algoritmos mais avançados como Quick Sort, Merge Sort e Heap Sort. Pratique implementando cada um e experimente com diferentes entradas para consolidar o aprendizado.

Perguntas Frequentes (FAQ)

Qual desses algoritmos é o mais rápido?

Insertion Sort tem o melhor desempenho médio para listas pequenas, mas todos têm complexidade O(n²). Para listas grandes, algoritmos como Quick Sort ou Merge Sort são mais adequados.

O que significa a estabilidade na prática?

Quando ordenamos uma tabela por uma coluna e depois por outra, queremos que a segunda ordenação preserve a ordenação anterior para valores iguais. Algoritmos estáveis garantem isso.

Posso usar esses algoritmos em listas com milhões de elementos?

Não, O(n²) torna o tempo proibitivo. Para grandes volumes, prefira algoritmos com O(n log n).

O Bubble Sort tem alguma vantagem real?

Além da simplicidade, com a otimização de parada ele pode ser eficiente para listas quase ordenadas. Também é estável e in-place.

Confira outros posts do blog para mais conteúdo de ciência da computação.