Ciências da computação dia 131

Nesta aula vamos estudar os algoritmos de ordenação mais fundamentais: Bubble Sort, Selection Sort e Insertion Sort. Veremos como funcionam, suas implementações em Python, análise de complexidade e quando utilizar cada um. Algoritmos de ordenação são uma parte essencial da ciência da computação, pois organizar dados de forma eficiente impacta diretamente o desempenho de buscas, análises e sistemas em geral. Apesar de existirem algoritmos mais avançados como Quick Sort e Merge Sort, compreender os algoritmos simples é crucial para construir uma base sólida. Hoje focaremos nos algoritmos elementares baseados em comparação.

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

Algoritmos de ordenação são procedimentos que reorganizam os elementos de uma sequência em uma determinada ordem — geralmente crescente ou decrescente. Eles podem ser classificados em várias categorias: algoritmos baseados em comparação (como os que estudaremos hoje) e algoritmos que não usam comparação (como Counting Sort ou Radix Sort). Outras classificações importantes incluem: ordenação interna (todos os dados cabem na memória principal) vs externa (quando os dados estão em disco); algoritmos estáveis (preservam a ordem relativa de elementos iguais) vs instáveis; algoritmos in-place (que não usam memória extra significativa) vs não in-place. Os algoritmos que veremos hoje são todos baseados em comparação, in-place e estáveis (com exceção do Selection Sort, que não é estável).

2. Bubble Sort

O Bubble Sort é um dos algoritmos mais simples de entender. O nome "Bubble" vem do fato de que elementos maiores "borbulham" para o final da lista. Ele percorre a lista repetidamente, comparando elementos adjacentes e trocando-os se estiverem fora de ordem. Esse processo é repetido até que nenhuma troca seja necessária, indicando que a lista está ordenada. Uma otimização comum é interromper o algoritmo se uma iteração completa não realizar nenhuma troca, melhorando o melhor caso para O(n). Apesar de sua simplicidade, o Bubble Sort é ineficiente para listas grandes, com complexidade O(n²) no pior caso. Veja a implementação com otimização:

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

Características: estável, in-place, adaptativo (pode parar cedo). É útil apenas para fins educacionais ou listas muito pequenas.

3. Selection Sort

O Selection Sort divide a lista em duas partes: uma parte ordenada à esquerda e uma parte não ordenada à direita. A cada iteração, procura o menor elemento na parte não ordenada e o troca com o primeiro elemento da parte não ordenada, expandindo a parte ordenada. Ele tem complexidade O(n²) em todos os casos, mas realiza menos trocas que o Bubble Sort (no máximo n-1 trocas). No entanto, ele não é estável, pois pode trocar elementos iguais de posição. Veja a implementação:

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

Apesar de ser O(n²) como os outros, o Selection Sort pode ser uma escolha razoável quando escrever na memória é caro (ex: flash memory), pois o número de escritas é mínimo. É também não adaptativo, pois sempre percorre toda a parte não ordenada.

4. Insertion Sort

O Insertion Sort constrói a lista ordenada um elemento de cada vez — análogo ao processo de ordenar cartas de baralho na mão, inserindo cada nova carta na posição correta. Para cada elemento (a partir do segundo), ele o insere na posição correta entre os elementos já ordenados, deslocando os maiores para a direita. É eficiente para listas pequenas ou quase ordenadas, com complexidade O(n) no melhor caso. É estável e in-place. Veja a implementação:

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

Na prática, o Insertion Sort é frequentemente usado como parte de algoritmos híbridos (como no TimSort) para ordenar pequenos subarrays. Sua boa localidade de referência e baixo overhead o tornam o mais rápido entre os três para listas com até algumas dezenas de elementos.

5. Comparação de Complexidades e Características

Todos os três algoritmos são in-place, usando apenas O(1) de espaço extra. Para arrays pequenos (até algumas centenas de elementos), o Insertion Sort geralmente é o mais rápido devido ao baixo overhead. Para arrays grandes, todos são lentos e recomenda-se algoritmos como Quick Sort, Merge Sort ou o sort nativo da linguagem (Timsort em Python).

6. Principais Pontos

• Algoritmos de ordenação são fundamentais para a computação e aparecem em entrevistas técnicas e sistemas reais.
• Bubble Sort, Selection Sort e Insertion Sort são algoritmos simples com complexidade O(n²).
• Insertion Sort é o mais eficiente entre os três para listas pequenas ou parcialmente ordenadas.
• Selection Sort minimiza o número de trocas, sendo útil quando a operação de escrita é cara.
• Bubble Sort pode ser otimizado com flag de parada, mas continua ineficiente para dados grandes.
• A escolha do algoritmo depende do tamanho dos dados, da necessidade de estabilidade e das restrições de memória.

7. Perguntas Frequentes

Qual a diferença entre Bubble Sort e Selection Sort?

Bubble Sort troca elementos adjacentes repetidamente durante toda a execução, enquanto Selection Sort seleciona o menor elemento a cada iteração e o coloca na posição correta. Selection Sort realiza muito menos trocas (no máximo n-1), mas é não adaptativo e não estável.

Por que Insertion Sort é mais rápido que os outros em listas pequenas?

Devido ao baixo overhead de instruções e à excelente localidade de referência — ele percorre um pequeno número de elementos a cada passo. Além disso, ele para cedo quando a lista já está parcialmente ordenada (melhor caso O(n)), diferente do Selection Sort que sempre executa O(n²) comparações.

Quais desses algoritmos são estáveis?

Bubble Sort e Insertion Sort são estáveis, ou seja, preservam a ordem relativa de elementos com chaves iguais. Selection Sort é instável, pois a troca pode deslocar um elemento igual para trás de outro.

Quando devo usar esses algoritmos em projetos reais?

Eles são adequados para listas com até algumas centenas de elementos ou quando a simplicidade de implementação é prioridade. Para conjuntos maiores, prefira algoritmos de divisão e conquista (Quick Sort, Merge Sort) ou a função de ordenação nativa da linguagem (Timsort em Python, por exemplo). Insertion Sort também é usado como base em algoritmos híbridos.

Qual a principal desvantagem do Bubble Sort?

É extremamente lento para listas grandes, realizando muitas comparações e trocas desnecessárias. Mesmo com a otimização de parada, seu desempenho é inferior aos demais algoritmos O(n²) na média, e muito inferior aos algoritmos avançados O(n log n).