Ciências da computação dia 229

Os algoritmos de ordenação são fundamentais na ciência da computação. Eles organizam elementos de uma lista em uma sequência específica — geralmente crescente ou decrescente — e são pré-requisito para algoritmos mais avançados como busca binária, análise de dados e otimização de consultas em bancos de dados. Nesta aula, vamos estudar quatro algoritmos clássicos: Bubble Sort, Insertion Sort, Merge Sort e Quick Sort, analisando suas complexidades de tempo e espaço, estabilidade e casos de uso ideais.

Bubble Sort

O Bubble Sort é o algoritmo mais simples de entender e implementar. Ele percorre a lista repetidamente, comparando elementos adjacentes e trocando-os se estiverem na ordem errada. A cada passagem, o maior elemento não ordenado "flutua" para sua posição correta no final da lista, como uma bolha na água — daí o nome.

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

Complexidade: O(n²) no pior caso (lista invertida), O(n) no melhor caso (lista já ordenada, com a otimização da flag swapped). Espaço auxiliar: O(1) — é in-place. Estável: sim. Apesar de simples e didático, o Bubble Sort raramente é usado em produção devido à baixa eficiência em listas com mais de alguns centenas de elementos.

Insertion Sort

O Insertion Sort constrói a lista ordenada incrementalmente. A cada iteração, um elemento é retirado da posição atual e inserido na posição correta entre os elementos já ordenados à sua esquerda. É exatamente o método que usamos intuitivamente para ordenar cartas de baralho na mão.

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

Complexidade: O(n²) no pior caso (lista invertida), O(n) no melhor caso (lista já ordenada ou quase ordenada). Espaço: O(1). Estável: sim. É eficiente para listas pequenas (menos de 50 elementos) ou quando os dados já estão parcialmente ordenados. Muitas implementações de Timsort usam Insertion Sort como sub-rotina para blocos pequenos.

Merge Sort

O Merge Sort é um algoritmo de dividir para conquistar. Ele divide a lista ao meio recursivamente até obter sublistas de um único elemento (que são naturalmente ordenadas), depois combina (merge) essas sublistas para produzir a lista final ordenada. A operação de mesclagem compara os primeiros elementos de cada sublista e insere o menor no resultado.

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

Complexidade: O(n log n) no pior caso, no melhor caso e no caso médio — desempenho previsível. Espaço: O(n) — não é in-place, pois requer memória auxiliar para as sublistas durante a mesclagem. Estável: sim. É amplamente utilizado quando estabilidade e desempenho previsível são necessários, especialmente em ordenação de listas encadeadas e dados que não cabem em memória principal.

Quick Sort

O Quick Sort também utiliza a estratégia de dividir para conquistar, mas com uma abordagem diferente. Ele seleciona um elemento como pivô, particiona a lista em elementos menores ou iguais e maiores que o pivô, e recursivamente ordena as partições. A escolha do pivô é crucial para o desempenho.

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

Complexidade: O(n²) no pior caso (pivô mal escolhido, como pegar o último elemento de uma lista já ordenada), O(n log n) no caso médio e no melhor caso. Espaço: O(log n) para a pilha de recursão. Não é estável na implementação clássica. Na prática, o Quick Sort é geralmente o algoritmo mais rápido para a maioria dos cenários, especialmente com escolha aleatória do pivô ou mediana de três.

Comparação entre os Algoritmos

Na prática, o Quick Sort é geralmente a escolha mais rápida para listas grandes não ordenadas, enquanto o Insertion Sort é útil para listas pequenas ou quase ordenadas. O Merge Sort é preferido quando a estabilidade é requisito ou quando os dados estão em estrutura que favorece acesso sequencial (listas encadeadas). Para a maioria das aplicações, as bibliotecas padrão das linguagens — como sorted() em Python (Timsort, uma mistura de Merge Sort e Insertion Sort) — já oferecem implementações altamente otimizadas.

Perguntas Frequentes

Qual algoritmo de ordenação devo usar no dia a dia?

Para a maioria dos casos, as funções prontas da linguagem são a melhor escolha. Em Python, o sorted() e o método .sort() implementam Timsort, que combina Merge Sort e Insertion Sort para obter desempenho O(n log n) com estabilidade. Em Java, o Arrays.sort() usa Dual-Pivot Quick Sort para tipos primitivos e Timsort para objetos. Entender os fundamentos ajuda a escolher a ferramenta certa e a escrever código mais eficiente quando você precisa implementar uma ordenação personalizada.

O que significa um algoritmo de ordenação ser estável?

Um algoritmo estável mantém a ordem relativa de elementos com chaves iguais. Se dois registros A e B têm o mesmo valor de ordenação e A aparece antes de B na lista original, após a ordenação A continuará antes de B. Isso é importante quando ordenamos por múltiplos critérios — por exemplo, ordenar uma lista de pessoas por nome e depois por idade: com um algoritmo estável, a ordenação por idade não desfaz a ordenação por nome.

O Bubble Sort tem alguma utilidade prática?

Fora do contexto educacional, o Bubble Sort raramente é usado. Seu principal valor é didático: é o algoritmo mais intuitivo para ensinar conceitos de ordenação, complexidade e otimização. Em cenários com listas muito pequenas (menos de 10 elementos) ou em sistemas embarcados com restrições extremas de memória, seu desempenho simples pode ser aceitável, mas o Insertion Sort quase sempre oferece melhor desempenho com a mesma simplicidade.

Merge Sort ou Quick Sort: qual é melhor?

Depende do contexto. O Quick Sort é geralmente mais rápido na prática para listas em memória (menor constante na notação O), mas tem o risco do pior caso O(n²) e não é estável. O Merge Sort oferece desempenho O(n log n) garantido e estabilidade, mas consome mais memória. Para listas encadeadas, o Merge Sort é naturalmente mais eficiente porque não requer acesso aleatório aos elementos. Em termos de uso geral, o Timsort (usado em Python e Java) combina o melhor dos dois mundos.