• Sabemos que o Shellsort é uma generalização do Insertion Sort. Implemente ambos os algoritmos e compare o desempenho com diferentes sequências de espaçamento (gap sequences) no Shellsort. Teste em vetores de 1000, 10.000 e 50.000 elementos.

Passo 1

Então, vamos lá! Você tem um exercício sobre algoritmos de ordenação, especificamente sobre o Insertion Sort e o Shellsort. A ideia é implementar esses dois algoritmos, testar o desempenho deles usando diferentes sequências de espaçamento (gap sequences) no Shellsort e comparar como eles se saem em vetores com 1.000, 10.000 e 50.000 elementos. Para resolver isso, vamos precisar entender como cada algoritmo funciona, saber implementar cada um e depois medir e comparar seus desempenhos.

Passo 2

Primeiro, vamos falar sobre o Insertion Sort. Esse algoritmo é bem direto: ele percorre o vetor da esquerda para a direita, e para cada elemento, ele o “insere” na posição correta em uma sublista que já está ordenada. É como se você estivesse organizando cartas na mão, pegando uma de cada vez e colocando na posição certa.
Aqui está como você pode implementar o Insertion Sort 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

Passo 3

Agora, vamos ao Shellsort. Ele é uma versão aprimorada do Insertion Sort. A principal diferença é que, no Shellsort, a gente começa comparando elementos que estão distantes uns dos outros, usando uma “sequência de gaps”. Isso ajuda a mover os elementos para suas posições corretas mais rapidamente. Depois, a distância entre os elementos comparados vai diminuindo até chegar a 1, onde o Shellsort se comporta como o Insertion Sort.
As gap sequences são fundamentais no Shellsort, pois elas determinam quais distâncias usar para comparar e organizar os elementos. Exemplos de sequências de gaps são:
  1. Sequência de Shell: começa com n/2 e divide por 2 a cada passo.
  2. Sequência de Knuth: usa gaps da forma $ \frac{3^k - 1}{2} $.
  3. Sequência de Sedgewick: combina múltiplos de potências de 2 e 3.
Vamos implementar o Shellsort permitindo diferentes sequências de gaps:
def shell_sort(arr, gaps):
    for gap in gaps:
        for i in range(gap, len(arr)):
            chave = arr[i]
            j = i
            while j >= gap and arr[j - gap] > chave:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = chave

Passo 4

Agora, precisamos preparar nossos vetores de teste com 1.000, 10.000 e 50.000 elementos. Vamos gerar listas com números aleatórios para cada tamanho. Em Python, podemos usar a biblioteca random para isso:
import random

vetor_1000 = random.sample(range(100000), 1000)
vetor_10000 = random.sample(range(1000000), 10000)
vetor_50000 = random.sample(range(1000000), 50000)

Passo 5

Com os vetores prontos, vamos testar o desempenho dos algoritmos. Para medir o tempo de execução, podemos usar o módulo time. Vamos executar o Insertion Sort e o Shellsort com diferentes sequências de gaps em cada vetor e registrar quanto tempo cada um leva.
import time

def medir_tempo(func, arr):
    inicio = time.time()
    func(arr)
    fim = time.time()
    return fim - inicio

# Definindo diferentes sequências de gaps
gaps_shell = [500, 250, 125, 62, 31, 15, 7, 3, 1]
gaps_knuth = []
k = 1
while True:
    gap = (3**k - 1) // 2
    if gap > len(vetor_50000):
        break
    gaps_knuth.insert(0, gap)
    k += 1

# Medindo tempos para Insertion Sort
tempo_insertion_1000 = medir_tempo(insertion_sort, vetor_1000.copy())
tempo_insertion_10000 = medir_tempo(insertion_sort, vetor_10000.copy())
tempo_insertion_50000 = medir_tempo(insertion_sort, vetor_50000.copy())

# Medindo tempos para Shellsort com diferentes gaps
tempo_shell_shell = medir_tempo(lambda x: shell_sort(x, gaps_shell), vetor_50000.copy())
tempo_shell_knuth = medir_tempo(lambda x: shell_sort(x, gaps_knuth), vetor_50000.copy())

Passo 6

Por fim, vamos comparar os tempos que cada algoritmo levou para ordenar os vetores. Isso vai nos dar uma ideia de qual algoritmo e quais sequências de gaps são mais eficientes para diferentes tamanhos de vetor.

Resposta

Após executar os testes, observamos que o Insertion Sort funciona bem para vetores menores, como o de 1.000 elementos. No entanto, seu desempenho diminui significativamente com vetores maiores, como 10.000 e especialmente 50.000 elementos. Já o Shellsort, especialmente com a sequência de Knuth, apresentou um desempenho muito melhor em vetores grandes, como o de 50.000 elementos, graças à redução eficiente das comparações necessárias. Portanto, para vetores grandes, o Shellsort com uma boa sequência de gaps é a melhor escolha em comparação com o Insertion Sort.

Exercícios relacionados