Durante nossas aulas de hoje, exploramos os principais algoritmos de ordenação utilizados em ciência da computação. A ordenação é uma operação fundamental que aparece como pré-requisito em diversos algoritmos mais complexos, como busca binária, análise estatística, compressão de dados e processamento de consultas em bancos de dados. Compreender como cada algoritmo funciona, suas vantagens e limitações é essencial para qualquer profissional da área.

Vamos analisar cada um dos algoritmos de ordenação mais importantes, começando pelos mais simples até chegar aos mais eficientes, incluindo implementações em pseudocódigo e análise de complexidade.

Bubble Sort

O Bubble Sort é um dos algoritmos mais simples de ordenação. Ele funciona percorrendo repetidamente a lista, comparando elementos adjacentes e trocando-os se estiverem na ordem errada. Este processo é repetido até que a lista esteja completamente ordenada.

O nome "Bubble" vem do fato de que os elementos maiores "borbulham" para o final da lista a cada iteração. Embora seja intuitivo e fácil de implementar, o Bubble Sort não é recomendado para conjuntos grandes de dados devido à sua baixa eficiência.

function bubbleSort(arr):
    n = length(arr)
    for i = 0 to n-1:
        for j = 0 to n-i-2:
            if arr[j] > arr[j+1]:
                swap(arr[j], arr[j+1])
    return arr

Complexidade: O(n²) no pior caso e O(n) no melhor caso (quando a lista já está ordenada e fazemos uma otimização com flag). Espaço: O(1).

Selection Sort

O Selection Sort (ordenação por seleção) divide a lista em duas partes: uma parte ordenada e outra não ordenada. A cada iteração, encontramos o menor elemento da parte não ordenada e o trocamos com o primeiro elemento desta parte, expandindo a parte ordenada.

Uma característica importante do Selection Sort é que ele faz no máximo O(n) trocas, o que pode ser vantajoso quando a operação de troca é muito cara. No entanto, ele sempre percorre toda a parte não ordenada, independentemente da lista estar parcialmente ordenada, o que resulta em complexidade O(n²) mesmo no melhor caso.

function selectionSort(arr):
    n = length(arr)
    for i = 0 to n-2:
        minIdx = i
        for j = i+1 to n-1:
            if arr[j] < arr[minIdx]:
                minIdx = j
        swap(arr[i], arr[minIdx])
    return arr>

Complexidade: O(n²) em todos os casos. Espaço: O(1). Não é estável.

Insertion Sort

O Insertion Sort (ordenação por inserção) constrói a lista ordenada um elemento por vez, inserindo cada novo elemento na posição correta em relação aos já ordenados. É como organizar cartas de baralho na mão: você pega uma carta e a insere na posição correta entre as cartas já ordenadas.

Este algoritmo é extremamente eficiente para listas pequenas ou quase ordenadas, com desempenho O(n) no melhor caso. Por isso, é frequentemente usado como parte de algoritmos mais avançados, como otimização em implementações de Quick Sort e Merge Sort para sublistas pequenas.

function insertionSort(arr):
    n = length(arr)
    for i = 1 to n-1:
        key = arr[i]
        j = i-1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j--
        arr[j+1] = key
    return arr

Complexidade: O(n) no melhor caso, O(n²) no pior caso. Espaço: O(1). É estável.

Quick Sort

O Quick Sort é um algoritmo de divisão e conquista desenvolvido por Tony Hoare. Ele escolhe um elemento como pivô e particiona a lista em duas sublistas: elementos menores que o pivô e elementos maiores. O processo é aplicado recursivamente às sublistas.

A escolha do pivô é crucial para o desempenho do Quick Sort. Estratégias comuns incluem escolher o primeiro elemento, o último elemento, o elemento do meio, ou usar a mediana de três elementos. Uma boa escolha de pivô ajuda a evitar o pior caso O(n²).

function quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    return arr

function partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j = low to high-1:
        if arr[j] ><= pivot:
            i++
            swap(arr[i], arr[j])
    swap(arr[i+1], arr[high])
    return i+1>

Complexidade: O(n log n) no caso médio, O(n²) no pior caso. Espaço: O(log n) para a pilha de recursão. Não é estável.

Merge Sort

O Merge Sort também utiliza a estratégia de divisão e conquista. Ele divide a lista ao meio recursivamente até obter sublistas de um elemento, que são ordenadas por natureza, e então intercala (merge) as sublistas para produzir a lista ordenada.

Diferentemente do Quick Sort, o Merge Sort tem complexidade O(n log n) garantida em todos os casos, mas requer O(n) de espaço adicional para a etapa de intercalação. É um algoritmo estável, o que o torna a escolha ideal quando a estabilidade é um requisito importante.

function mergeSort(arr):
    if length(arr) <= 1:
        return arr
    mid = length(arr) // 2
    left = mergeSort(arr[0:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)

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

Complexidade: O(n log n) em todos os casos. Espaço: O(n). É estável.

Heap Sort

O Heap Sort utiliza uma estrutura de dados chamada heap (max-heap) para ordenar os elementos. Primeiro, construímos um max-heap a partir dos dados, e então extraímos repetidamente o maior elemento, colocando-o no final da lista.

O Heap Sort combina a eficiência O(n log n) com uso de espaço O(1), mas não é estável. Na prática, é menos utilizado que Quick Sort e Merge Sort devido a um desempenho um pouco inferior em termos de constantes e localidade de referência.

function heapSort(arr):
    n = length(arr)
    for i = n/2-1 down to 0:
        heapify(arr, n, i)
    for i = n-1 down to 0:
        swap(arr[0], arr[i])
        heapify(arr, i, 0)
    return arr

function heapify(arr, n, i):
    largest = i
    left = 2*i + 1
    right = 2*i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        swap(arr[i], arr[largest])
        heapify(arr, n, largest)

Complexidade: O(n log n) em todos os casos. Espaço: O(1). Não é estável.

Tabela comparativa

Algoritmo Melhor caso Caso médio Pior caso Espaço Estável
Bubble Sort O(n) O(n²) O(n²) O(1) Sim
Selection Sort O(n²) O(n²) O(n²) O(1) Não
Insertion Sort O(n) O(n²) O(n²) O(1) Sim
Quick Sort O(n log n) O(n log n) O(n²) O(log n) Não
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Sim
Heap Sort O(n log n) O(n log n) O(n log n) O(1) Não

Quando usar cada algoritmo

A escolha do algoritmo de ordenação depende do contexto e dos requisitos específicos da aplicação:

Para listas pequenas (n ≤ 50): Insertion Sort é geralmente a melhor escolha devido à sua simplicidade e bom desempenho com dados quase ordenados. É também a escolha ideal quando os dados chegam em tempo real e precisam ser inseridos em uma lista já ordenada.

Para aplicações de uso geral: Quick Sort é a escolha padrão na maioria das bibliotecas (como a qsort do C e Arrays.sort do Java para tipos primitivos) por seu bom desempenho médio e uso eficiente de memória. A maioria das implementações utiliza a mediana de três para escolha do pivô e muda para Insertion Sort para sublistas pequenas.

Quando estabilidade é necessária: Merge Sort ou TimSort (uma combinação de Merge Sort e Insertion Sort) são as melhores opções. Python e JavaScript utilizam TimSort como algoritmo padrão de ordenação porque ele combina a estabilidade do Merge Sort com a eficiência do Insertion Sort para dados parcialmente ordenados.

Para datasets muito grandes que não cabem em memória: Merge Sort é a base para algoritmos de ordenação externa (external sorting), pois seu padrão de acesso sequencial é eficiente para memória secundária.

Quando a memória é limitada: Heap Sort ou Quick Sort (in-place) são preferíveis, pois usam apenas O(log n) ou O(1) de espaço adicional. Heap Sort tem a vantagem de ter complexidade O(n log n) garantida sem usar espaço extra da pilha de recursão.

Perguntas frequentes

O que significa a notação O(n log n)?
A notação Big O descreve como o tempo de execução do algoritmo cresce com o tamanho da entrada. O(n log n) significa que o tempo de execução é proporcional a n multiplicado pelo logaritmo de n, o que é considerado eficiente para algoritmos de ordenação. Para n = 1 milhão, um algoritmo O(n log n) executa aproximadamente 20 milhões de operações, enquanto um O(n²) executaria 1 trilhão.

Por que Quick Sort é mais rápido que Merge Sort na prática?
Apesar de ambos terem complexidade O(n log n) no caso médio, o Quick Sort tem melhor localidade de referência (acesso sequencial à memória) e menores constantes na implementação. Além disso, o Merge Sort requer O(n) de espaço extra para o array auxiliar, o que aumenta o custo de alocação e cópia de memória.

O que é um algoritmo de ordenação estável?
Um algoritmo estável preserva a ordem relativa de elementos com chaves iguais. Por exemplo, se temos dois registros com a mesma chave de ordenação, um algoritmo estável mantém a ordem original desses registros. Isso é importante quando os dados já estão ordenados por um critério secundário e queremos manter essa ordenação ao aplicar um novo critério.

Qual é o melhor algoritmo de ordenação?
Não existe um "melhor" algoritmo universal. A escolha depende do tamanho dos dados, da distribuição, da necessidade de estabilidade, da disponibilidade de memória e se os dados já estão parcialmente ordenados. Para a maioria dos casos práticos, Quick Sort ou TimSort oferecem o melhor equilíbrio entre desempenho e uso de recursos. O mais importante é entender as características de cada algoritmo para fazer a escolha certa para cada situação.