Nesta aula, mergulhamos nos algoritmos de ordenação mais fundamentais da computação. A ordenação é uma operação central em praticamente todos os sistemas computacionais, desde bancos de dados até interfaces de usuário. Compreender como os algoritmos funcionam internamente é essencial para qualquer cientista da computação. Focamos em três algoritmos clássicos — Bubble Sort, Selection Sort e Insertion Sort — analisando seus mecanismos passo a passo, sua complexidade assintótica e implementações práticas em Python.

Embora existam algoritmos mais eficientes (como Merge Sort ou Quick Sort), os algoritmos O(n²) são didáticos e formam a base para entender análise de algoritmos. Além disso, em cenários com poucos dados ou listas quase ordenadas, eles podem ser competitivos.

O que é ordenação?

Ordenação é o processo de rearranjar os elementos de uma sequência de acordo com uma ordem pré-definida (crescente, decrescente, lexicográfica, etc.). Os algoritmos de ordenação são um dos tópicos mais estudados na ciência da computação porque aparecem como sub-rotina em inúmeras aplicações.

Todo algoritmo de ordenação pode ser caracterizado por sua complexidade de tempo e espaço, estabilidade e se é comparativo ou não. Os três algoritmos estudados são comparativos, ou seja, baseiam-se em comparações entre elementos para decidir a ordem.

Bubble Sort

O Bubble Sort percorre repetidamente a lista, comparando elementos adjacentes e trocando-os se estiverem na ordem errada. O processo é repetido até que nenhuma troca seja necessária, indicando que a lista está ordenada. O nome “bolha” vem do fato de que os maiores elementos “flutuam” para o final da lista a cada iteração.

Complexidade:

  • Melhor caso: O(n) – quando a lista já está ordenada (com a otimização de interrupção).
  • Pior caso e caso médio: O(n²).
  • Espaço: O(1) – in-place.
  • Estável: sim.

Implementação em Python:

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

Exemplo passo a passo: Para a lista [5, 1, 4, 2, 8], a primeira passagem compara 5 e 1 (troca), 5 e 4 (troca), 5 e 2 (troca), 5 e 8 (mantém), resultando em [1, 4, 2, 5, 8]. O processo se repete até a lista estar ordenada.

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, encontra o menor elemento da parte não ordenada e o troca com o primeiro elemento dessa parte, expandindo a parte ordenada.

Complexidade:

  • Todos os casos: O(n²) – não se beneficia de listas parcialmente ordenadas.
  • Espaço: O(1) – in-place.
  • Estável: não (por padrão; a versão estável requer mais movimento).

Implementação em Python:

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

Exemplo passo a passo: Lista [29, 10, 14, 37, 13]. Na primeira iteração, encontra o menor (10) e troca com o primeiro (29): [10, 29, 14, 37, 13]. Depois, encontra o menor entre os restantes (13) e troca com 29: [10, 13, 14, 37, 29], e assim sucessivamente.

Insertion Sort

O Insertion Sort constrói a lista ordenada um elemento de cada vez, inserindo cada novo elemento na posição correta em relação aos já ordenados. É análogo à forma como muitas pessoas ordenam cartas de baralho.

Complexidade:

  • Melhor caso: O(n) – lista já ordenada (apenas comparações).
  • Pior caso e caso médio: O(n²).
  • Espaço: O(1) – in-place.
  • Estável: sim.

Implementação em Python:

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

Exemplo passo a passo: Lista [5, 2, 4, 6, 1, 3]. O elemento na posição 1 (2) é inserido antes de 5: [2, 5, 4, 6, 1, 3]. O 4 é inserido entre 2 e 5: [2, 4, 5, 6, 1, 3]. O 6 permanece, e o 1 é movido para o início, e assim por diante.

Comparação entre os algoritmos

AlgoritmoMelhor casoPior casoEstávelMemória extra
Bubble SortO(n)O(n²)SimO(1)
Selection SortO(n²)O(n²)NãoO(1)
Insertion SortO(n)O(n²)SimO(1)

Observe que o Selection Sort é o único que não é estável, e ele também não se beneficia de listas ordenadas. O Insertion Sort é geralmente o mais eficiente entre os três em listas pequenas ou quase ordenadas, sendo usado como sub-rotina em algoritmos híbridos como o TimSort.

Quando usar cada algoritmo?

  • Bubble Sort: apenas para fins didáticos ou quando se deseja um código muito simples e a lista é muito pequena.
  • Selection Sort: quando o custo de troca é alto (porque faz no máximo n-1 trocas) e a lista é pequena.
  • Insertion Sort: ideal para listas pequenas (até ~50 elementos) ou listas que já estão quase ordenadas. É o algoritmo recomendado entre os três para uso prático em cenários limitados.

Vale lembrar que, para conjuntos grandes, algoritmos como Merge Sort (O(n log n)) são mais adequados.

Perguntas Frequentes

Qual a diferença entre Bubble Sort e Selection Sort?
Enquanto o Bubble Sort troca elementos adjacentes repetidamente, o Selection Sort encontra o menor elemento e o coloca na posição correta em uma única troca por iteração. O Selection Sort geralmente faz menos trocas, mas ambas as complexidades são O(n²).
O que significa estabilidade em um algoritmo de ordenação?
Um algoritmo é estável se mantém a ordem relativa de elementos com chaves iguais. Isso é importante quando a lista já está ordenada por outro critério e queremos preservar a ordenação anterior.
Posso usar Insertion Sort em produção?
Sim, para listas muito pequenas ou como parte de um algoritmo híbrido. Por exemplo, o TimSort (usado em Python e Java) utiliza Insertion Sort para sub-listas de até 64 elementos.

Conclusão

Os algoritmos de ordenação O(n²) são essenciais para a formação de qualquer profissional de computação. Eles nos ensinam sobre análise de complexidade, invariantes de loop e a importância de escolher a ferramenta certa para cada problema. A prática de implementá-los e testá-los com diferentes tipos de entrada solidifica conceitos que serão levados para algoritmos mais avançados.

Nos próximos artigos, avançaremos para algoritmos mais eficientes como Merge Sort, Quick Sort e algoritmos não comparativos. Fique ligado!