Hoje exploramos um dos tópicos mais importantes da computação: a análise de complexidade de algoritmos e os principais métodos de ordenação. Entender como medir a eficiência de um algoritmo e conhecer as vantagens de cada técnica de ordenação é essencial para qualquer profissional da área. Vamos revisar os conceitos vistos em aula e analisar implementações clássicas.

Análise de complexidade: notação Big O

A notação Big O descreve o limite superior do tempo de execução de um algoritmo em função do tamanho da entrada. As classes mais comuns são:

  • O(1) – tempo constante (acesso direto a um array);
  • O(log n) – tempo logarítmico (busca binária);
  • O(n) – tempo linear (percorrer um array);
  • O(n log n) – comum em algoritmos de ordenação eficientes (Merge Sort, Quick Sort);
  • O(n²) – tempo quadrático (Bubble Sort, Selection Sort).

Na aula, comparamos o crescimento dessas funções e discutimos como escolher o algoritmo certo para cada cenário. Lembre-se: a análise assintótica nos ajuda a prever o comportamento para entradas grandes, mas fatores constantes e características do hardware também importam.

Algoritmos de ordenação elementares

Revisitamos os algoritmos de ordenação mais simples, que servem como base para entender os mais avançados.

Bubble Sort

O Bubble Sort compara pares adjacentes e troca-os se estiverem na ordem errada, repetindo o processo até que o array esteja ordenado. Sua complexidade é O(n²) no pior caso.

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

Selection Sort

O Selection Sort encontra o menor elemento da parte não ordenada e o coloca no início. Também O(n²), mas faz menos trocas que o Bubble Sort.

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

Algoritmos de ordenação eficientes

Para conjuntos grandes, os algoritmos O(n log n) são muito superiores. Vimos os dois mais importantes:

Merge Sort

Baseado na estratégia de dividir para conquistar: divide o array ao meio, ordena cada metade recursivamente e depois intercala as metades ordenadas.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Quick Sort

O Quick Sort escolhe um pivô, particiona o array em elementos menores e maiores que o pivô, e ordena as partições recursivamente. No caso médio é O(n log n), mas o pior caso (pivô mal escolhido) é O(n²).

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Comparação prática

Testamos os algoritmos com um array de 10 mil elementos aleatórios. O Merge Sort e o Quick Sort completaram em milissegundos, enquanto o Bubble Sort levou vários segundos. Isso ilustra na prática a importância da análise de complexidade.

Resumo dos pontos principais

  • A notação Big O é a ferramenta padrão para comparar eficiência de algoritmos.
  • Algoritmos O(n²) são adequados apenas para entradas pequenas.
  • Merge Sort e Quick Sort são muito mais rápidos para grandes volumes de dados.
  • A escolha do algoritmo depende do contexto: estabilidade, uso de memória e tamanho dos dados.
  • É possível combinar estratégias (ex.: usar Insertion Sort para subarrays pequenos dentro do Quick Sort) para ganhos práticos.

Perguntas frequentes

Qual a diferença entre Merge Sort e Quick Sort?

Merge Sort sempre executa em O(n log n) e é estável, mas requer memória auxiliar O(n). Quick Sort é in-place (não usa memória extra significativa), mas seu pior caso é O(n²); na prática, com boas escolhas de pivô, é geralmente mais rápido que Merge Sort.

Quando usar Bubble Sort?

Raramente. Ele é útil apenas para arrays quase ordenados (com uma variante otimizada que detecta trocas) ou fins didáticos. Para qualquer outro cenário, prefira algoritmos mais eficientes.

O que significa “in-place”?

Um algoritmo in-place ordena os dados sem precisar de uma quantidade significativa de memória extra além do próprio array. Selection Sort e Quick Sort (versão clássica) são in-place; Merge Sort não é.

Como escolher entre Quick Sort e Merge Sort no dia a dia?

Se você precisa de estabilidade e previsibilidade, Merge Sort é a escolha segura. Se a memória é limitada e os dados são grandes, Quick Sort é preferível. Muitas bibliotecas padrão (como Python’s Timsort) usam uma mistura de Merge Sort e Insertion Sort para obter o melhor dos dois mundos.