Ciências da computação dia 108

Introdução

Hoje vamos estudar algoritmos de ordenação, um dos tópicos mais clássicos e importantes da computação. Ordenar dados é uma operação fundamental que aparece em inúmeras aplicações, desde a organização de listas até a otimização de consultas em bancos de dados. Existem muitas formas de ordenar, cada uma com suas vantagens e desvantagens. Neste artigo, vamos explorar os cinco algoritmos mais conhecidos: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort e Quick Sort. Para cada um, veremos o princípio de funcionamento, a implementação em Python e a complexidade assintótica. Vamos começar.

Bubble Sort

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

A complexidade no pior e médio caso é O(n²), o que o torna ineficiente para listas grandes. Porém, é fácil de implementar e útil para aprendizado.

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 divide a lista em duas partes: uma parte ordenada e outra não ordenada. A cada iteração, ele seleciona o menor elemento da parte não ordenada e o troca com o primeiro elemento não ordenado. Assim, a parte ordenada cresce uma posição por vez.

Assim como o Bubble Sort, sua complexidade é O(n²) em todos os casos. Ele é útil quando o número de trocas precisa ser mínimo, pois realiza no máximo n trocas.

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>

Insertion Sort

O Insertion Sort funciona de forma semelhante à maneira como organizamos cartas de baralho: percorremos a lista e inserimos cada elemento na posição correta entre os já ordenados. É eficiente para listas pequenas ou parcialmente ordenadas, com complexidade O(n²) no pior caso, mas próximo de O(n) quando os dados já estão quase ordenados.

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>

Merge Sort

O Merge Sort é um algoritmo de ordenação por intercalação que utiliza a estratégia de dividir para conquistar. Ele divide a lista recursivamente em duas metades até que cada sublista tenha apenas um elemento, depois intercala (merge) as sublistas de forma ordenada. Sua complexidade é O(n log n) no pior caso, e é estável (mantém a ordem relativa de elementos iguais).

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 também usa dividir para conquistar, mas com uma abordagem diferente: escolhe um elemento como pivô, particiona a lista em três partes (menores, iguais e maiores que o pivô) e ordena recursivamente as partes. Na média, sua complexidade é O(n log n), mas no pior caso (quando o pivô é mal escolhido) pode chegar a O(n²). Na prática, é um dos algoritmos mais rápidos e amplamente utilizado.

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 dos Algoritmos

Cada algoritmo tem seus pontos fortes e fracos. A tabela a seguir resume as complexidades de tempo e espaço:

Perguntas Frequentes

Qual o melhor algoritmo de ordenação?

Não existe um "melhor" absoluto; a escolha depende do contexto. Para listas pequenas, Insertion Sort é simples e eficiente. Para grandes volumes, Merge Sort e Quick Sort são preferíveis. Quick Sort é geralmente o mais rápido na prática, mas Merge Sort é estável e tem garantia de O(n log n).

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

Um algoritmo é estável quando preserva a ordem relativa de elementos com chaves iguais. Por exemplo, se dois registros têm o mesmo valor de ordenação, eles aparecerão na mesma ordem em que estavam na entrada original. Merge Sort e Insertion Sort são estáveis; Quick Sort não é necessariamente.

O Quick Sort pode ser O(n²)?

Sim, se o pivô for sempre o menor ou o maior elemento (por exemplo, em uma lista já ordenada e escolhendo o primeiro elemento como pivô). Isso pode ser mitigado com boas estratégias de escolha do pivô, como mediana de três ou pivô aleatório.

O Merge Sort sempre gasta mais memória?

Sim, porque ele cria novas listas durante a intercalação. Sua complexidade de espaço é O(n), enquanto os algoritmos in-place (como Quick Sort, Selection Sort, Insertion Sort) usam apenas O(1) ou O(log n) de espaço extra.

Conclusão

Estudar algoritmos de ordenação é essencial para entender conceitos fundamentais de ciência da computação, como complexidade, recursão e estratégias de projeto. Cada algoritmo tem seu lugar, e saber quando usar cada um é uma habilidade valiosa. Continue praticando e explorando outros artigos da série Ciências da computação para aprofundar seus conhecimentos.