- Implemente o algoritmo de Insertion Sort para ordenar um vetor de números inteiros. Teste com vetores de tamanhos variados e exiba o tempo de execução.
Passo 1
Ok, vamos resolver esse exercício juntos! A questão pede para implementar o algoritmo de Insertion Sort para ordenar um vetor de números inteiros, testar com vetores de tamanhos variados e exibir o tempo de execução. Para isso, vamos precisar entender como funciona o Insertion Sort, saber como implementar em uma linguagem de programação (vamos usar Python), e como medir o tempo de execução.
Passo 2
Primeiro, vamos entender o que é o Insertion Sort. É um algoritmo de ordenação que constrói a lista final ordenada um elemento de cada vez. Ele é eficiente para listas pequenas e funciona de maneira semelhante à forma como você ordena cartas na mão.
Passo 3
Agora, vamos implementar o Insertion Sort em Python. Vamos criar uma função que recebe uma lista de números inteiros e a ordena usando o Insertion Sort.
def insertion_sort(arr):
for i in range(1, len(arr)):
chave = arr[i]
j = i - 1
while j >=0 and chave < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = chave
return arr
Passo 4
Vamos entender o que esse código faz:
- for i in range(1, len(arr)): começa a iterar do segundo elemento até o final da lista.
- chave = arr[i]: guarda o valor atual que vamos inserir na posição correta.
- j = i - 1: começa a comparar com os elementos anteriores.
- while j >=0 and chave < arr[j]: enquanto não chegarmos ao início e o elemento anterior for maior que a chave, deslocamos o elemento para a direita.
- arr[j + 1] = chave: coloca a chave na posição correta.
Passo 5
Agora, vamos testar a função com vetores de tamanhos variados. Também vamos medir o tempo de execução usando o módulo
time
.import time
import random
def test_insertion_sort():
tamanhos = [10, 100, 1000, 2000]
for tamanho in tamanhos:
# Gerando um vetor aleatório
vetor = [random.randint(0, 10000) for _ in range(tamanho)]
# Copiando o vetor para não alterar o original
vetor_para_sort = vetor.copy()
# Medindo o tempo de execução
inicio = time.time()
insertion_sort(vetor_para_sort)
fim = time.time()
print(f"Tamanho do vetor: {tamanho} - Tempo de execução: {fim - inicio:.6f} segundos")
Passo 6
Explicando esse código:
- tamanhos = [10, 100, 1000, 2000]: define diferentes tamanhos de vetores para testar.
- random.randint(0, 10000): gera números aleatórios entre 0 e 10.000.
- time.time(): captura o tempo antes e depois da ordenação para calcular a duração.
- print: exibe o tamanho do vetor e o tempo que levou para ordenar.
Passo 7
Vamos rodar a função de teste para ver os resultados:
test_insertion_sort()
Resposta
Ao executar o código, você verá uma saída semelhante a esta (os tempos podem variar dependendo do seu computador):
Tamanho do vetor: 10 - Tempo de execução: 0.000012 segundos
Tamanho do vetor: 100 - Tempo de execução: 0.000143 segundos
Tamanho do vetor: 1000 - Tempo de execução: 0.009857 segundos
Tamanho do vetor: 2000 - Tempo de execução: 0.039654 segundos
Isso mostra que o algoritmo Insertion Sort funciona corretamente e que o tempo de execução aumenta conforme o tamanho do vetor aumenta.