Ciências da computação dia 137

Hoje na aula de Ciências da Computação, continuamos nosso estudo sobre algoritmos de ordenação. Estes algoritmos são fundamentais para organizar dados e servem de base para muitas operações, como busca binária, análise de dados e otimização de outros algoritmos. Nesta aula, exploramos quatro algoritmos clássicos: Bubble Sort, Insertion Sort, Merge Sort e Quick Sort, analisando suas implementações, complexidades e características.

Introdução

Algoritmos de ordenação organizam uma sequência de elementos de acordo com uma ordem específica (geralmente crescente ou decrescente). A eficiência de um algoritmo de ordenação é medida pelo seu tempo de execução em relação ao tamanho da entrada (n) e pelo uso de memória adicional. Além disso, propriedades como estabilidade (preservar a ordem de elementos iguais) e in-place (ordenar usando apenas a própria estrutura de dados, sem alocar muito espaço extra) são importantes na escolha do algoritmo certo para cada situação.

Bubble Sort

O Bubble Sort é o algoritmo mais simples de entender. Ele percorre a lista diversas vezes, comparando elementos adjacentes e trocando-os se estiverem na ordem errada. A cada passagem o maior elemento "flutua" para o final da lista, como uma bolha. O processo se repete até que nenhuma troca seja necessária.

Implementação em Python:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

Complexidade: O(n²) no pior e médio caso, O(n) no melhor caso (lista já ordenada). É estável e in-place.

Insertion Sort

O Insertion Sort constrói a lista final incrementalmente. Ele seleciona um elemento de cada vez e o insere na posição correta dentro da porção já ordenada, deslocando os demais para a direita. É intuitivo e eficiente para listas pequenas ou quase ordenadas.

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: O(n²) no pior caso, O(n) no melhor. Estável e in-place.

Merge Sort

O Merge Sort adota a estratégia de divisão e conquista. Ele divide a lista ao meio recursivamente até que cada sublista tenha um único elemento, depois intercala (merge) as sublistas ordenadas para formar a lista final ordenada.

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]
        merge_sort(L)
        merge_sort(R)
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr

Complexidade: O(n log n) em todos os casos. É estável, mas não é in-place, pois requer espaço auxiliar O(n).

Quick Sort

O Quick Sort também usa divisão e conquista, mas de maneira diferente: escolhe um elemento como pivô e particiona a lista em duas: elementos menores ou iguais ao pivô e elementos maiores. Em seguida, ordena recursivamente as partições. É um dos algoritmos mais rápidos na prática.

def quicksort(arr, low=0, high=None):
    if high is None:
        high = len(arr)-1
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi-1)
        quicksort(arr, pi+1, high)
    return arr

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

Complexidade: O(n log n) no caso médio, O(n²) no pior caso (quando a escolha do pivô é desfavorável). É in-place, mas não é estável.

Comparação e Considerações Finais

A escolha do algoritmo depende do volume de dados e dos requisitos de estabilidade e uso de memória. Para listas muito pequenas, Insertion Sort é uma boa opção. Para listas grandes, Merge Sort e Quick Sort oferecem melhor desempenho. Merge Sort é estável e tem complexidade garantida, mas consome mais memória. Quick Sort é mais rápido na média e trabalha in-place, porém pode ser instável e degenerar para O(n²) em casos específicos.

A tabela a seguir resume as principais características dos algoritmos estudados:

Em Python, a função nativa sorted() utiliza Timsort — híbrido de Merge Sort e Insertion Sort — que oferece bom desempenho geral. Entender os algoritmos clássicos, no entanto, é essencial para dominar os fundamentos da computação.

FAQ — Perguntas Frequentes

O que significa um algoritmo ser estável?
Algoritmos estáveis mantêm a ordem relativa de elementos com valores iguais. Por exemplo, ao ordenar alunos por nota, a ordem de quem tirou a mesma nota é preservada. Isso é importante em ordenações múltiplas (como ordenar por sobrenome e depois por nota).

Por que usamos a notação Big O?
A notação Big O descreve como o tempo de execução cresce conforme o tamanho da entrada aumenta, desconsiderando constantes e particularidades da implementação. Ela nos permite comparar algoritmos de forma teórica e independente de hardware.

Qual algoritmo devo usar no dia a dia?
Na maioria dos casos, utilize a função de ordenação da sua linguagem (como sorted() do Python). Se for implementar manualmente, Quick Sort é uma escolha sólida para listas grandes, e Insertion Sort é útil para listas pequenas ou quase ordenadas.