Ciências da computação dia 104

Hoje mergulhamos nos algoritmos de ordenação, pilares fundamentais da ciência da computação. Estudamos o Bubble Sort, Insertion Sort e Quick Sort, analisando suas lógicas, implementações passo a passo em Python, complexidade temporal e espacial, e casos de uso ideais.

Bubble Sort (Ordenação por Bolha)

O Bubble Sort é um algoritmo simples que percorre repetidamente a lista, compara elementos adjacentes e os troca se estiverem na ordem errada. O processo é repetido até que a lista esteja ordenada. Embora não seja eficiente para grandes conjuntos de dados, é amplamente usado para fins didáticos devido à sua simplicidade.

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

Complexidade:

• Melhor caso: O(n) (com otimização de parada antecipada)
• Caso médio e pior caso: O(n²)
• Espaço auxiliar: O(1)

É um algoritmo estável (a ordem relativa de elementos iguais é preservada) e fácil de implementar, porém lento para listas com mais de algumas dezenas de elementos.

Insertion Sort (Ordenação por Inserção)

O Insertion Sort constrói a lista ordenada um elemento por vez: a cada iteração, retira um elemento da posição atual e o insere na posição correta entre os já ordenados. É o método que muitas pessoas usam intuitivamente ao ordenar cartas de baralho.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        chave = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > chave:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = chave
    return arr

Complexidade:

• Melhor caso: O(n) (lista já ordenada)
• Caso médio e pior caso: O(n²)
• Espaço auxiliar: O(1)

Assim como o Bubble Sort, é estável e tem complexidade quadrática no pior caso, mas na prática é mais eficiente que o Bubble Sort para listas pequenas ou parcialmente ordenadas.

Quick Sort (Ordenação Rápida)

O Quick Sort adota a estratégia dividir para conquistar. Escolhe um elemento como pivô, particiona a lista em duas sublistas — uma com elementos menores e outra com elementos maiores que o pivô — e recursivamente ordena cada sublista. É um dos algoritmos mais rápidos na prática.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivo = arr[len(arr) // 2]
    esquerda = [x for x in arr if x < pivo]
    meio = [x for x in arr if x == pivo]
    direita = [x for x in arr if x > pivo]
    return quick_sort(esquerda) + meio + quick_sort(direita)>

Complexidade:

• Melhor caso: O(n log n)
• Caso médio: O(n log n)
• Pior caso: O(n²) (quando o pivô é sempre o menor ou maior elemento)
• Espaço auxiliar: O(log n) (devido à recursão)

O Quick Sort não é estável na implementação clássica, mas com escolha aleatória do pivô ou mediana de três, o risco do pior caso é minimizado, tornando‑o extremamente eficiente para grandes volumes de dados.

Comparação de complexidades

Perguntas frequentes

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

Depende do contexto. Para listas pequenas (menos de 50 elementos) ou quase ordenadas, Insertion Sort é simples e eficiente. Para listas grandes, Quick Sort oferece o melhor desempenho médio. Bubble Sort é mais indicado para aprendizado, não para produção.

O Quick Sort é sempre a melhor escolha?

Não. Em cenários com restrições de memória ou quando a estabilidade é necessária, algoritmos como Merge Sort podem ser mais adequados. Além disso, se os dados já estiverem quase ordenados, o Insertion Sort pode superar o Quick Sort devido ao baixo overhead.

Algoritmos de ordenação têm aplicação no mundo real?

Sim, vasta. São usados em bancos de dados para ordenar resultados de consultas ORDER BY, em sistemas de arquivos para organizar listagens, em algoritmos de busca e recomendação, e em praticamente toda aplicação que manipula coleções de dados.