- 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:
- Sequência de Shell: começa com n/2 e divide por 2 a cada passo.
- Sequência de Knuth: usa gaps da forma $ \frac{3^k - 1}{2} $.
- 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.