Nesta aula, abordamos três algoritmos de ordenação clássicos: Bubble Sort, Selection Sort e Insertion Sort. Embora não sejam os mais eficientes para grandes conjuntos de dados, eles são fundamentais para entender os princípios de ordenação por comparação e servem como base para algoritmos mais avançados como Merge Sort e Quick Sort.

Vamos analisar o funcionamento de cada algoritmo, sua complexidade de tempo e apresentar implementações em Python.

Bubble Sort

O Bubble Sort funciona comparando pares adjacentes e trocando-os se estiverem na ordem errada. Esse processo é repetido até que nenhuma troca seja necessária. A cada iteração, o maior elemento “flutua” para o final da lista, como uma bolha.

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

Complexidade: Melhor caso O(n) (lista já ordenada), pior caso O(n²) (lista invertida). Espaço adicional O(1).

Selection Sort

O Selection Sort divide a lista em duas partes: a parte ordenada (à esquerda) e a parte não ordenada (à direita). A cada passo, encontra o menor elemento da parte não ordenada e o troca com o primeiro elemento dessa parte. O algoritmo não é estável, pois trocas podem desordenar elementos iguais.

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. Espaço extra O(1). Não é estável.

Insertion Sort

O Insertion Sort percorre a lista da esquerda para a direita e, para cada elemento, o insere na posição correta na parte já ordenada (à esquerda). É eficiente para listas pequenas ou parcialmente ordenadas e é estável.

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: Melhor caso O(n) (lista já ordenada), pior caso O(n²). Estável, O(1) espaço extra.

Comparação dos Algoritmos

Algoritmo Melhor Caso Caso Médio Pior Caso Estável Memória Extra
Bubble Sort O(n) O(n²) O(n²) Sim O(1)
Selection Sort O(n²) O(n²) O(n²) Não O(1)
Insertion Sort O(n) O(n²) O(n²) Sim O(1)

Perguntas Frequentes

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

O Bubble Sort realiza trocas sucessivas entre pares adjacentes, enquanto o Selection Sort encontra o menor elemento a cada iteração e o troca diretamente com a posição correta. O Selection Sort geralmente faz menos trocas, mas ambas têm complexidade O(n²).

Quando usar Insertion Sort?

Insertion Sort é preferível quando a lista já está parcialmente ordenada ou é muito pequena, pois seu melhor caso é O(n). É também estável e simples de implementar.

Selection Sort é estável?

Não, o Selection Sort não é estável porque a troca do menor elemento pode deslocar um elemento igual para a frente de outro igual, alterando a ordem relativa original.