• 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.

Exercícios relacionados