Ciências da computação dia 263

Nesta aula, vamos estudar três algoritmos de ordenação clássicos: Insertion Sort, Merge Sort e Quick Sort. Veremos seus princípios, implementações em Python e análise de complexidade. Esses algoritmos são fundamentais para a compreensão de estruturas de dados e análise de algoritmos.

Insertion Sort

O Insertion Sort é um algoritmo simples que constrói a lista ordenada um elemento por vez. Ele percorre a lista da esquerda para a direita e insere cada elemento na posição correta entre os elementos já ordenados.

Passos do algoritmo:

• Percorra o array a partir do segundo elemento.
• Compare o elemento atual com os anteriores.
• Se o elemento anterior for maior, desloque-o para a direita.
• Insira o elemento na posição correta.

Complexidade:

• Melhor caso: O(n) – quando o array já está ordenado.
• Pior caso: O(n²) – quando o array está inversamente ordenado.
• Caso médio: O(n²).

Implementação em Python:

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

O Insertion Sort é eficiente para listas pequenas ou parcialmente ordenadas. É estável e opera in-place.

Merge Sort

O Merge Sort é um algoritmo de ordenação baseado na técnica de dividir para conquistar. Ele divide recursivamente a lista em metades até que cada sublista tenha apenas um elemento, depois mescla as sublistas de forma ordenada.

Passos do algoritmo:

• Divida a lista ao meio recursivamente.
• Ordene cada metade recursivamente.
• Mescle as duas metades ordenadas em uma única lista ordenada.

Complexidade:

• Todos os casos: O(n log n) – pois sempre divide e mescla.
• Espaço auxiliar: O(n) – necessita de arrays auxiliares.

Implementação em Python:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    esq = merge_sort(arr[:mid])
    dir = merge_sort(arr[mid:])
    return merge(esq, dir)

def merge(esq, dir):
    resultado = []
    i = j = 0
    while i >< len(esq) and j >< len(dir):
        if esq[i] ><= dir[j]:
            resultado.append(esq[i])
            i += 1
        else:
            resultado.append(dir[j])
            j += 1
    resultado.extend(esq[i:])
    resultado.extend(dir[j:])
    return resultado>

Merge Sort é estável e tem complexidade garantida O(n log n), porém requer memória extra.

Quick Sort

O Quick Sort também utiliza a abordagem de dividir para conquistar, mas de forma diferente: escolhe um pivô e particiona a lista em elementos menores e maiores que o pivô, ordenando recursivamente as partições.

Passos do algoritmo:

• Escolha um pivô (geralmente o último elemento).
• Particione o array: coloque elementos menores que o pivô à esquerda e maiores à direita.
• Aplique recursivamente o Quick Sort nas partições.

Complexidade:

• Melhor caso: O(n log n) – quando o pivô divide exatamente ao meio.
• Pior caso: O(n²) – quando o pivô é o menor ou maior elemento.
• Caso médio: O(n log n).

Implementação em Python:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivo = arr[-1]
    menores = [x for x in arr[:-1] if x ><= pivo]
    maiores = [x for x in arr[:-1] if x > pivo]
    return quick_sort(menores) + [pivo] + quick_sort(maiores)

Existem implementações in-place do Quick Sort que evitam o uso extra de memória, mas a versão acima é mais didática.

Comparação entre os algoritmos

Considerações finais

A escolha do algoritmo de ordenação depende do contexto: para listas pequenas, Insertion Sort é simples e eficiente; para grandes volumes, Merge Sort oferece estabilidade e desempenho previsível; Quick Sort é rápido na prática, mas pode degenerar. Conhecer esses algoritmos é essencial para qualquer cientista da computação.

Perguntas frequentes

Qual a diferença entre Merge Sort e Quick Sort?

Merge Sort divide a lista exatamente ao meio, garantindo O(n log n) em todos os casos, mas exige memória extra. Quick Sort particiona em torno de um pivô, é mais rápido na média e pode ser in-place, mas tem pior caso O(n²).

Quando usar Insertion Sort?

Insertion Sort é recomendado para listas pequenas (até ~50 elementos) ou quase ordenadas. É simples de implementar e eficiente nesses cenários.

O Quick Sort é sempre rápido?

Não. Se o pivô for mal escolhido (ex.: menor ou maior elemento), o Quick Sort pode ter desempenho O(n²). Por isso, em implementações reais, usa-se pivô aleatório ou mediana de três para mitigar esse problema.