Hoje vamos mergulhar no mundo dos algoritmos de ordenação. Na aula passada, discutimos a importância de organizar dados; agora vamos colocar a mão na massa com implementações simples em Python. Algoritmos de ordenação são fundamentais porque nos permitem buscar dados eficientemente, identificar duplicatas e preparar informações para outros processamentos. Sem eles, operações como busca binária ou junção de grandes conjuntos seriam inviáveis na prática.

Vamos começar com três algoritmos clássicos — Bubble Sort, Selection Sort e Insertion Sort — que, apesar de não serem os mais rápidos para grandes volumes, são didáticos e nos ajudam a compreender conceitos essenciais de complexidade e lógica de programação. Implementaremos cada um em Python e analisaremos seu comportamento.

O que é um algoritmo de ordenação?

Um algoritmo de ordenação é um procedimento computacional que rearranja os elementos de uma lista em uma determinada ordem — geralmente crescente ou decrescente. Existem dezenas de algoritmos, cada um com suas vantagens e desvantagens. Os três que veremos hoje são classificados como algoritmos simples (ou elementares) e são ideais para conjuntos de dados pequenos ou para fins educacionais.

Bubble Sort

O Bubble Sort percorre repetidamente a lista, compara elementos adjacentes e os troca se estiverem na ordem errada. O nome "bubble" vem do fato de que os elementos maiores "borbulham" para o final a cada iteração. O processo se repete até que nenhuma troca seja necessária, indicando que a lista está ordenada.

Implementação em Python:

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

Análise de complexidade: No pior caso (lista invertida), o Bubble Sort executa O(n²) comparações e trocas. No melhor caso (lista já ordenada), com uma versão otimizada que detecta se houve troca, pode alcançar O(n). É um algoritmo estável e in-place.

Selection Sort

O Selection Sort divide a lista em duas partes: a parte ordenada (à esquerda) e a parte não ordenada (à direita). A cada iteração, ele seleciona o menor elemento da parte não ordenada e o coloca no final da parte ordenada. Apesar de simples, ele sempre executa o mesmo número de comparações, independentemente da ordem inicial.

Implementação em Python:

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr>

Análise de complexidade: O Selection Sort realiza O(n²) comparações em todos os casos (melhor, médio e pior), mas faz no máximo O(n) trocas. Isso pode ser vantajoso quando o custo de escrever na memória é alto. Não é um algoritmo estável, pois a troca direta pode alterar a ordem relativa de elementos iguais.

Insertion Sort

O Insertion Sort constrói a lista ordenada um elemento por vez. A cada iteração, ele pega um elemento da parte não ordenada e o insere na posição correta entre os elementos já ordenados. É o mesmo raciocínio de organizar cartas em uma mão de baralho.

Implementação em Python:

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>

Análise de complexidade: O Insertion Sort tem complexidade O(n²) no pior e médio caso, mas é eficiente para listas pequenas ou parcialmente ordenadas, podendo chegar a O(n). É estável e in-place, e na prática costuma ser mais rápido que os outros dois para conjuntos com até 20–30 elementos.

Comparação de desempenho

A tabela abaixo resume as principais características dos três algoritmos:

AlgoritmoMelhor CasoPior CasoEstávelIn-place
Bubble SortO(n)O(n²)SimSim
Selection SortO(n²)O(n²)NãoSim
Insertion SortO(n)O(n²)SimSim

Observamos que, apesar de todos terem complexidade quadrática no pior caso, o Insertion Sort é geralmente preferível para listas pequenas ou quase ordenadas. O Selection Sort pode ser útil quando o custo de troca é elevado, enquanto o Bubble Sort — embora didático — raramente é usado em aplicações reais (exceto em versões otimizadas para conjuntos muito pequenos).

Conclusão

Nesta aula, aprendemos os três algoritmos de ordenação mais básicos. Eles nos ensinam sobre loops aninhados, troca de variáveis e análise de complexidade. Esses conceitos são a base para algoritmos mais avançados que veremos nos próximos dias, como Merge Sort, Quick Sort e Heap Sort.

Exercício recomendado: implemente uma versão otimizada do Bubble Sort que interrompa a execução se nenhuma troca for feita em uma iteração. Teste com listas de diferentes tamanhos e compare o tempo de execução com os outros algoritmos.

Continue acompanhando as aulas para dominar cada vez mais os fundamentos da ciência da computação. Até a próxima!

Perguntas Frequentes

Por que o Selection Sort não é estável?

O Selection Sort não é estável porque ele seleciona o menor elemento e o troca diretamente com o elemento da posição atual. Se houver elementos iguais, a troca pode alterar a ordem relativa entre eles. Por exemplo, na lista [5a, 3, 5b], ao selecionar o 3 (primeira iteração), ele troca com o 5a, fazendo com que o 5a fique depois do 5b — alterando a ordem original.

O Insertion Sort é bom para conjuntos pequenos?

Sim! O Insertion Sort é muito eficiente para listas com até 20–30 elementos, especialmente se elas já estão parcialmente ordenadas. Por isso, muitos algoritmos avançados (como o Timsort, usado no Python) usam Insertion Sort como sub-rotina para partes pequenas do array.

O Bubble Sort tem alguma utilidade prática?

Embora seja principalmente didático, versões otimizadas do Bubble Sort podem ser usadas em sistemas embarcados com recursos mínimos ou quando se deseja um código extremamente simples e curto. No entanto, para aplicações reais, prefere-se algoritmos mais eficientes como Quick Sort ou Merge Sort.