Ciências da computação dia 171

Nesta aula, exploramos os principais algoritmos de ordenação, que são fundamentais para a organização eficiente de dados. A ordenação permite que buscas sejam realizadas de forma mais rápida e é base para muitos outros algoritmos. Veremos os algoritmos clássicos — Bubble Sort, Selection Sort, Insertion Sort, Quick Sort e Merge Sort — analisando suas complexidades, estabilidade e aplicações práticas.

O que é ordenação?

Ordenação é o processo de reorganizar um conjunto de elementos em uma ordem específica, geralmente crescente ou decrescente. Os algoritmos de ordenação são avaliados principalmente pela sua complexidade de tempo (número de comparações e trocas) e espaço (memória adicional utilizada). Além disso, a estabilidade é uma propriedade importante: um algoritmo é estável se mantém a ordem relativa de elementos iguais.

Bubble Sort

O Bubble Sort é um dos algoritmos mais simples de implementar. Ele percorre o array repetidamente, comparando elementos adjacentes e trocando-os se estiverem na ordem errada. O processo é repetido até que nenhuma troca seja necessária, o que indica que o array está ordenado.

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

Complexidade: O(n²) no pior caso e O(n) no melhor caso (com otimização de parada). Espaço: O(1). Estável: sim. Embora seja ineficiente para grandes conjuntos, é útil para fins didáticos e para arrays muito pequenos.

Selection Sort

O Selection Sort divide o array em duas partes: a parte ordenada (à esquerda) e a parte não ordenada (à direita). A cada iteração, seleciona o menor elemento da parte não ordenada e o troca com o primeiro elemento não ordenado, expandindo a parte ordenada.

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>

Complexidade: O(n²) em todos os casos (não há otimização significativa). Espaço: O(1). Estável: não (a troca pode desfazer a ordem de elementos iguais). É simples e tem a vantagem de realizar no máximo O(n) trocas, o que pode ser útil quando a operação de troca é muito cara.

Insertion Sort

O Insertion Sort constrói a ordenação final um elemento por vez. Ele percorre o array da esquerda para a direita e insere cada elemento na posição correta em relação aos elementos já ordenados, deslocando os maiores para a direita.

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 caso (array já ordenado). Espaço: O(1). Estável: sim. Muito eficiente para arrays pequenos ou quase ordenados, sendo frequentemente usado em combinação com algoritmos mais complexos (ex.: Timsort).

Quick Sort

O Quick Sort utiliza a estratégia de divisão e conquista. Ele escolhe um elemento como pivô e particiona o array em dois subarrays: elementos menores que o pivô à esquerda e maiores à direita. Depois, ordena recursivamente cada subarray. A escolha do pivô influencia diretamente o desempenho.

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)

Complexidade: média O(n log n), pior caso O(n²) (quando o pivô é mal escolhido). Espaço: O(log n) devido à recursão. Estável: não (a versão clássica in-place não é estável). Na prática, com uma boa estratégia de pivô (aleatório ou mediana de três), Quick Sort é geralmente o mais rápido entre os algoritmos de ordenação geral.

Merge Sort

O Merge Sort também é baseado em divisão e conquista. Ele divide o array ao meio recursivamente até obter subarrays de um elemento, depois intercala (merge) os subarrays ordenados de forma a gerar um array ordenado. Ele é muito previsível, com desempenho consistente.

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>

Complexidade: O(n log n) no pior, melhor e caso médio. Espaço: O(n) (necessita de arrays auxiliares). Estável: sim. É ideal para ordenar listas encadeadas e para situações onde a estabilidade é necessária, mas o uso extra de memória pode ser uma desvantagem.

Comparação de Complexidade

A tabela abaixo resume as características dos algoritmos estudados:

Dúvidas Frequentes

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

Um algoritmo estável preserva a ordem relativa de elementos com chaves iguais. Por exemplo, ao ordenar uma lista de alunos por nota, dois alunos com a mesma nota mantêm a posição original que tinham antes da ordenação. Insertion Sort e Merge Sort são estáveis; Quick Sort (versão clássica) e Selection Sort não são.

Qual algoritmo devo usar no dia a dia?

Na maioria das linguagens de programação, as funções nativas de ordenação (como sort() do Python) utilizam Timsort — uma mistura de Merge Sort e Insertion Sort — que é eficiente e estável. Para uso geral em projetos, prefira algoritmos com complexidade O(n log n), como Merge Sort ou Quick Sort. Insertion Sort é útil para listas pequenas (menos de 50 elementos) ou quase ordenadas.

O Quick Sort é sempre a melhor escolha?

Não. No pior caso (array já ordenado com pivô fixo na ponta), Quick Sort degrada para O(n²). Porém, na prática, com escolha aleatória de pivô ou mediana de três, isso é muito raro. Merge Sort é mais previsível (sempre O(n log n)) e estável, mas consome mais memória. A escolha depende dos requisitos do problema: se a estabilidade é crucial ou a memória é limitada, Merge Sort ou Quick Sort in-place podem ser preferidos.

Hoje vimos os cinco algoritmos de ordenação mais clássicos. Compreender seus pontos fortes e fracos é essencial para escolher a melhor estratégia em cada situação. Continue praticando e confira outros posts sobre ciência da computação em nosso blog.