Ciências da computação dia 107

Nesta aula, vamos estudar três algoritmos de ordenação clássicos: Bubble Sort, Insertion Sort e Selection Sort. Algoritmos de ordenação são fundamentais na ciência da computação, pois organizam dados de forma eficiente, permitindo buscas e análises mais rápidas. Vamos entender o funcionamento de cada um, sua complexidade e quando utilizá-los.

Bubble Sort

O Bubble Sort percorre a lista repetidamente, comparando elementos adjacentes e trocando-os se estiverem fora de ordem. O processo se repete até que nenhuma troca seja necessária.

1. Compare o primeiro e o segundo elemento. Se o primeiro for maior, troque-os.
2. Compare o segundo e o terceiro, e assim por diante até o final da lista.
3. Ao final da primeira passada, o maior elemento já está na última posição.
4. Repita o processo para os primeiros n-1 elementos, ignorando o último.
5. Continue até que uma passada inteira não realize nenhuma troca.

• Complexidade: O(n²) no pior caso e O(n) no melhor caso (lista já ordenada).
• Estável: sim.
• In-place: sim.

Insertion Sort

O Insertion Sort constrói a lista ordenada um elemento de cada vez, inserindo cada novo elemento na posição correta entre os já ordenados.

1. Considere o primeiro elemento como ordenado.
2. Pegue o próximo elemento e compare com os anteriores, deslocando os maiores para a direita.
3. Insira o elemento na posição correta.
4. Repita até que todos os elementos estejam na posição correta.

• Complexidade: O(n²) no pior caso, O(n) no melhor caso.
• Estável: sim.
• In-place: sim.

Selection Sort

O Selection Sort seleciona repetidamente o menor elemento da parte não ordenada e o coloca no início da lista.

1. Encontre o menor elemento na lista.
2. Troque-o com o primeiro elemento.
3. Considere o primeiro elemento como ordenado.
4. Repita para a sublista restante (a partir do segundo elemento).

• Complexidade: O(n²) em todos os casos.
• Não estável (exceto se implementado com cuidado).
• In-place: sim.

Comparação entre os Algoritmos

A tabela abaixo resume as principais diferenças:

Análise de Complexidade

A notação Big O descreve o comportamento assintótico dos algoritmos. No pior caso, todos os três algoritmos apresentam complexidade O(n²), o que significa que o tempo de execução cresce quadraticamente com o tamanho da entrada. Para entradas pequenas, essa diferença é imperceptível. O Bubble Sort pode ser otimizado com a flag swapped, enquanto o Insertion Sort se destaca em listas parcialmente ordenadas. O Selection Sort possui desempenho constante O(n²) independentemente da ordenação inicial.

Implementação em Python

Veja abaixo a implementação de cada algoritmo:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break
    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):
    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

No código acima, bubble_sort utiliza a flag swapped para interromper o algoritmo se a lista já estiver ordenada. insertion_sort percorre a lista e insere cada elemento na posição correta deslocando os maiores. selection_sort encontra o menor elemento e o troca com o primeiro da parte não ordenada. Todos os algoritmos modificam a lista original (in-place).

Vantagens e Desvantagens

• Bubble Sort: Simples de implementar, porém ineficiente para listas grandes. Pode ser otimizado com a flag de troca.
• Insertion Sort: Eficiente para listas pequenas ou quase ordenadas. É utilizado como base em algoritmos mais avançados (Timsort).
• Selection Sort: Simples, mas com desempenho quadrático constante. Útil quando o custo de troca é baixo.

Perguntas Frequentes

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

O Bubble Sort realiza trocas consecutivas a cada comparação, enquanto o Selection Sort primeiro encontra o menor elemento e depois realiza uma única troca por passada.

Quando usar Insertion Sort?

Insertion Sort é ideal para listas pequenas (até 50 elementos) ou quase ordenadas, onde seu desempenho se aproxima de O(n).

O que significa um algoritmo ser "in-place"?

Significa que o algoritmo ordena os dados utilizando apenas uma quantidade constante de memória extra, modificando o array original.

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

Porque a troca direta do menor elemento com o primeiro pode deslocar elementos iguais de sua ordem relativa.