Hoje, na disciplina de Ciências da Computação, dedicamos a aula aos algoritmos de ordenação. Ordenar dados é uma operação fundamental em computação, presente em sistemas de bancos de dados, interfaces de usuário e processamento de grandes volumes de informação. Estudamos três algoritmos clássicos — Bubble Sort, Selection Sort e Insertion Sort — analisando seu funcionamento, complexidade e aplicações práticas.

O que é um algoritmo de ordenação?

Um algoritmo de ordenação organiza os elementos de uma sequência (como um array ou lista) em uma ordem específica, geralmente crescente ou decrescente. A ordenação facilita buscas, otimiza processos e é base para muitos outros algoritmos. Existem dezenas de métodos, cada um com suas vantagens. Hoje focamos nos algoritmos simples e intuitivos, ideais para conjuntos pequenos de dados ou para fins educacionais.

Bubble Sort

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

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Complexidade: O(n²) no pior caso, O(n) no melhor caso (quando já ordenada). É um algoritmo estável (preserva a ordem de elementos iguais) e pode ser implementado com poucas linhas.

Selection Sort

O Selection Sort (ordenação por seleção) divide a lista em duas partes: a parte ordenada (à esquerda) e a parte não ordenada (à direita). A cada passo, seleciona o menor elemento da parte não ordenada e o troca com o primeiro elemento dessa parte. Assim, a fronteira da parte ordenada avança um elemento por iteração.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        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, pois sempre percorre a parte não ordenada. Não é estável (a troca pode alterar a ordem relativa de elementos iguais). Seu número de trocas é reduzido (no máximo n‑1), o que pode ser vantajoso em situações onde escrever na memória é caro.

Insertion Sort

O Insertion Sort (ordenação por inserção) constrói a lista ordenada um elemento de cada vez. Ele percorre a lista da esquerda para a direita e insere cada elemento na posição correta entre os elementos já ordenados, deslocando os maiores para a direita.

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

Complexidade: O(n²) no pior e médio caso, O(n) no melhor caso (lista já ordenada). É estável e eficiente para listas pequenas ou quase ordenadas. É o algoritmo preferido para ordenar pequenos conjuntos em muitas aplicações reais.

Comparação de desempenho

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

Algoritmo Pior caso Melhor caso Estável Troca máxima
Bubble Sort O(n²) O(n) Sim O(n²)
Selection Sort O(n²) O(n²) Não O(n)
Insertion Sort O(n²) O(n) Sim O(n²) (deslocamentos)

Quando usar cada um?

  • Bubble Sort: didático, raramente usado em produção devido ao alto número de trocas.
  • Selection Sort: útil quando o custo de troca é elevado (poucas trocas), mas não é estável.
  • Insertion Sort: excelente para listas pequenas ou quase ordenadas; usado internamente em algoritmos mais avançados (como Timsort).

Conclusão

Os algoritmos de ordenação simples são a porta de entrada para o estudo de complexidade e técnicas de projeto de algoritmos. Embora não sejam os mais rápidos para grandes volumes, sua compreensão é essencial para qualquer estudante de computação. Recomendo praticar as implementações e testar com diferentes entradas para fixar os conceitos.

Perguntas frequentes (FAQ)

Qual a diferença entre Bubble Sort e Insertion Sort?

Ambos são O(n²), mas Insertion Sort geralmente faz menos comparações em listas parcialmente ordenadas e é mais eficiente na prática. Bubble Sort realiza muitas trocas mesmo quando a lista está próxima da ordenação.

O Selection Sort é melhor que o Bubble Sort?

Em número de trocas, sim — Selection Sort faz no máximo n‑1 trocas, enquanto Bubble Sort pode fazer O(n²) trocas. No entanto, o número de comparações é o mesmo (O(n²)). Para dados grandes, ambos são lentos; prefira algoritmos como Merge Sort ou Quick Sort.

Onde posso ver mais algoritmos de ordenação?

Explore outros artigos no Posts ou procure por tags como algoritmos para conteúdo adicional sobre complexidade e implementações.