Ciências da computação dia 222 — Algoritmos de Ordenação

Nesta aula, vamos explorar três algoritmos de ordenação clássicos: Bubble Sort, Insertion Sort e Selection Sort. Eles são os primeiros passos para entender como podemos organizar dados de forma eficiente. A ordenação é uma operação fundamental em computação, utilizada em diversas aplicações, desde organização de listas até indexação de bancos de dados.

Bubble Sort

O Bubble Sort, ou ordenação por bolha, é um dos algoritmos mais simples de entender. Ele funciona percorrendo repetidamente a lista, comparando elementos adjacentes e trocando-os se estiverem na ordem errada. Esse processo se repete até que nenhuma troca seja necessária, indicando que a lista está ordenada.

Vamos considerar um exemplo com o array [5, 3, 8, 1]:

Primeira passagem: compara 5 e 3 → troca (3, 5, 8, 1); compara 5 e 8 → mantém; compara 8 e 1 → troca (3, 5, 1, 8).
Segunda passagem: (3, 5, 1, 8) → compara 3 e 5 mantém; 5 e 1 troca (3, 1, 5, 8); 5 e 8 mantém.
Terceira passagem: (3, 1, 5, 8) → 3 e 1 troca (1, 3, 5, 8); 3 e 5 mantém; fim.

Ao final, temos o array ordenado.

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

O Bubble Sort tem complexidade O(n²) no pior caso (quando a lista está invertida) e O(n) no melhor caso (quando já está ordenada, se implementarmos uma otimização). No entanto, em média, é O(n²), tornando-o ineficiente para grandes conjuntos de dados.

Insertion Sort

O Insertion Sort constrói a lista ordenada gradualmente. Para cada elemento, ele encontra a posição correta inserindo-o na parte já ordenada, deslocando os elementos maiores para a direita. É o algoritmo que muitas pessoas usam intuitivamente ao ordenar cartas de baralho.

Exemplo com [5, 3, 8, 1]:

Começa com 5 (já ordenado).
Pega 3, compara com 5, desloca 5 para a direita e insere 3 na posição 0: [3, 5, 8, 1].
Pega 8, já está maior que 5, mantém: [3, 5, 8, 1].
Pega 1, desloca 8,5,3 para a direita e insere 1 no início: [1, 3, 5, 8].

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 também é O(n²) no pior caso, mas seu melhor caso é O(n) quando a lista já está ordenada. Ele é eficiente para listas pequenas ou parcialmente ordenadas, sendo até mesmo utilizado como componente de algoritmos híbridos como o Timsort.

Selection Sort

O Selection Sort funciona selecionando repetidamente o menor elemento da parte não ordenada e trocando-o com o primeiro elemento não ordenado. Ele é intuitivo, porém não é estável (a ordem relativa de elementos iguais pode ser alterada).

Exemplo com [5, 3, 8, 1]:

Menor elemento é 1, troca com 5: [1, 3, 8, 5].
Agora ordenado começa em índice 1: menor entre [3,8,5] é 3, mantém.
Entre [8,5] menor é 5, troca com 8: [1,3,5,8].

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 tem complexidade O(n²) independentemente da ordem inicial. Embora simples, seu desempenho é inferior ao Insertion Sort na prática para a maioria dos cenários. A principal vantagem é que ele faz no máximo O(n) trocas, o que pode ser útil quando escrever na memória é caro.

Comparação entre os Algoritmos

A tabela abaixo resume as principais características:

Algoritmo	Melhor Caso	Pior Caso	Estável
Bubble Sort	O(n)	O(n²)	Sim
Insertion Sort	O(n)	O(n²)	Sim
Selection Sort	O(n²)	O(n²)	Não

Pontos-Chave

Bubble Sort, Insertion Sort e Selection Sort são algoritmos de ordenação O(n²) no pior caso.
Insertion Sort é o mais eficiente entre eles para listas pequenas ou quase ordenadas.
Selection Sort não é estável e faz sempre O(n²) comparações, mas o número de trocas é O(n).
Para grandes volumes de dados, devemos optar por algoritmos como Merge Sort, Quick Sort ou Heap Sort.

Perguntas Frequentes

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

O Bubble Sort realiza trocas sucessivas entre pares adjacentes até ordenar, enquanto o Insertion Sort insere cada elemento na posição correta deslocando os demais. O Insertion Sort costuma ser mais rápido em listas pequenas.

2. O Selection Sort é estável?

A implementação padrão do Selection Sort não é estável, pois a troca do menor elemento com o primeiro pode alterar a ordem relativa de elementos iguais.

3. Qual desses algoritmos devo usar no dia a dia?

Em linguagens de programação, funções de ordenação nativas já implementam algoritmos eficientes (como Timsort no Python). Mas entender esses três algoritmos é fundamental para aprender análises e técnicas mais avançadas.