Durante as aulas de hoje, vimos os três algoritmos de ordenação clássicos: Bubble Sort, Insertion Sort e Selection Sort. Esses algoritmos são fundamentais para entender como os computadores organizam dados e servem de base para algoritmos mais complexos. A seguir estão as anotações completas com pseudocódigo e análise de complexidade.

Bubble Sort

O Bubble Sort é o algoritmo mais simples de ordenação. Ele funciona percorrendo a lista repetidamente, comparando elementos adjacentes e trocando-os se estiverem fora de ordem. A cada passagem, o maior elemento "flutua" para a posição correta, como uma bolha. O processo continua até que nenhuma troca seja necessária.

procedimento bubbleSort(A: lista de elementos)
    n = tamanho(A)
    para i = 0 até n-1
        para j = 0 até n-i-2
            se A[j] > A[j+1] então
                trocar(A[j], A[j+1])
            fim se
        fim para
    fim para
fim procedimento

Complexidade: no pior caso O(n²), no melhor caso O(n) (quando já ordenada). É um algoritmo estável, porém ineficiente para grandes conjuntos de dados.

Para visualizar o funcionamento do Bubble Sort, considere o array [5, 3, 8, 4, 2]. Na primeira iteração externa (i=0), o loop interno percorre j=0 até 3: compara 5 e 3 e troca → [3,5,8,4,2]; compara 5 e 8, não troca; compara 8 e 4 e troca → [3,5,4,8,2]; compara 8 e 2 e troca → [3,5,4,2,8]. Ao final da primeira passagem, o maior elemento (8) está na última posição. Na segunda iteração, o processo repete para os primeiros n-1 elementos. A ordenação termina quando nenhuma troca é realizada em uma passagem completa.

Insertion Sort

O Insertion Sort constrói a lista ordenada um elemento de cada vez. Ele percorre a lista e insere cada elemento na posição correta em relação aos já ordenados. É análogo ao modo como organizamos cartas de baralho.

procedimento insertionSort(A: lista de elementos)
    n = tamanho(A)
    para i = 1 até n-1
        chave = A[i]
        j = i - 1
        enquanto j >= 0 e A[j] > chave
            A[j+1] = A[j]
            j = j - 1
        fim enquanto
        A[j+1] = chave
    fim para
fim procedimento

Complexidade: pior caso O(n²), melhor caso O(n). É estável e eficiente para listas pequenas ou parcialmente ordenadas.

Para entender o Insertion Sort, usamos o mesmo array [5,3,8,4,2]. Consideramos o primeiro elemento (5) como ordenado. O segundo (3) é comparado e inserido à esquerda → [3,5,8,4,2]. O terceiro (8) é maior que 5, permanece. O quarto (4) percorre o segmento ordenado e é inserido entre 3 e 5 → [3,4,5,8,2]. Por fim, o 2 é inserido no início → [2,3,4,5,8]. Esse algoritmo realiza apenas deslocamentos, sem trocas excessivas, sendo especialmente eficiente para listas pequenas ou parcialmente ordenadas.

Selection Sort

O Selection Sort divide a lista em duas partes: ordenada e não ordenada. A cada iteração, seleciona o menor elemento da parte não ordenada e o coloca no final da parte ordenada. É intuitivo mas ineficiente.

procedimento selectionSort(A: lista de elementos)
    n = tamanho(A)
    para i = 0 até n-2
        min = i
        para j = i+1 até n-1
            se A[j] < A[min] então
                min = j
            fim se
        fim para
        trocar(A[i], A[min])
    fim para
fim procedimento

Complexidade: O(n²) em todos os casos. Não é estável, pois pode trocar elementos iguais de posição.

Com o mesmo array [5,3,8,4,2], o Selection Sort busca o menor elemento em toda a lista: encontra o valor 2 na última posição e troca com o primeiro (5) → [2,3,8,4,5]. Na segunda iteração, o menor a partir do índice 1 é o 3, que já está na posição correta. Na terceira, encontra o 4 e troca com o 8 → [2,3,4,8,5]. Na quarta, encontra o 5 e troca com o 8 → [2,3,4,5,8]. Apesar de realizar muitas comparações, o número de trocas é no máximo n-1, o que pode ser vantajoso quando a operação de troca é custosa.

Comparação de Complexidades

Algoritmo Melhor Caso Caso Médio Pior Caso
Bubble SortO(n)O(n²)O(n²)
Insertion SortO(n)O(n²)O(n²)
Selection SortO(n²)O(n²)O(n²)

Estabilidade e Adaptabilidade

A estabilidade de um algoritmo de ordenação indica se a ordem relativa de elementos com chaves iguais é preservada após a ordenação. O Bubble Sort e o Insertion Sort são estáveis, pois realizam trocas apenas entre elementos adjacentes e não pulam elementos iguais. O Selection Sort não é estável, porque a troca entre um elemento distante e o primeiro da parte não ordenada pode inverter a posição relativa de elementos iguais. A adaptabilidade diz respeito ao desempenho quando a lista já está parcialmente ordenada. O Insertion Sort é altamente adaptativo, atingindo complexidade O(n) em listas quase ordenadas. O Bubble Sort pode tornar-se adaptativo com uma otimização simples (flag de troca). Já o Selection Sort não é adaptativo: seu desempenho é sempre O(n²), independentemente da ordenação inicial. Quanto ao uso de memória, todos os três algoritmos são in-place, ou seja, utilizam apenas espaço auxiliar constante O(1).

Resumo dos Algoritmos

  • Bubble Sort: simples e estável, porém ineficiente para listas grandes. Ideal apenas para fins didáticos.
  • Insertion Sort: estável, adaptativo e eficiente para listas quase ordenadas. Ótimo para poucos elementos.
  • Selection Sort: não estável, número fixo de trocas. O desempenho não é afetado pela ordem inicial.

Implementações em Python

Abaixo estão as implementações em Python para os três algoritmos discutidos:

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
def insertion_sort(arr):
    for i in range(1, len(arr)):
        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
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

Perguntas Frequentes

Qual o melhor algoritmo para listas pequenas?

O Insertion Sort é geralmente o mais indicado, pois possui baixo overhead e é adaptativo, aproveitando ordenações parciais.

Quando usar Bubble Sort na prática?

O Bubble Sort não é recomendado para aplicações reais devido à sua ineficiência. Seu uso fica restrito a contextos educacionais.

Qual algoritmo faz o menor número de trocas?

O Selection Sort realiza no máximo n-1 trocas, o que é vantajoso quando a operação de troca é cara.

O Selection Sort é estável? Por quê?

O Selection Sort não é estável. A cada iteração, ocorre uma troca entre o elemento selecionado (menor) e o primeiro elemento da parte não ordenada. Se houver elementos iguais, essa troca pode fazer com que um deles ultrapasse o outro, alterando a ordem relativa original.

É possível otimizar o Bubble Sort?

Sim, a otimização mais comum é introduzir uma flag booleana que indica se houve troca em uma passagem completa. Se nenhuma troca ocorrer, o array já está ordenado e o algoritmo pode ser interrompido. Essa versão otimizada mantém a estabilidade e tem melhor caso O(n).

Qual é a principal vantagem do Insertion Sort sobre os demais?

O Insertion Sort é adaptativo: seu tempo de execução aproxima-se de O(n) quando a lista está quase ordenada. Além disso, possui baixo overhead, é estável e eficiente para listas com poucos elementos, tornando-o a escolha mais prática entre os três algoritmos clássicos para cenários do dia a dia.

Conclusão

Nesta aula, exploramos os algoritmos Bubble Sort, Insertion Sort e Selection Sort em detalhe. Compreendemos seus mecanismos, analisamos suas complexidades e discutimos propriedades importantes como estabilidade e adaptabilidade. Embora sejam pouco eficientes para grandes conjuntos de dados, esses algoritmos são fundamentais para a construção do raciocínio sobre ordenação e servem de base para o estudo de métodos mais avançados, como Merge Sort, Quick Sort e Heap Sort. Dominar esses conceitos é essencial para qualquer estudante de ciência da computação.