- Implemente uma função que utilize Quicksort até que o tamanho do subvetor seja menor que 10, e então use Insertion Sort para ordenar esses pequenos subvetores.
Compare o tempo de execução com a versão padrão do Quicksort.
Compare o tempo de execução com a versão padrão do Quicksort.
Passo 1
Vamos resolver um exercício que envolve algoritmos de ordenação, especificamente o Quicksort e o Insertion Sort. A tarefa é implementar uma função que usa Quicksort para ordenar um vetor, mas quando o tamanho de um subvetor fica menor que 10 elementos, usa o Insertion Sort para ordenar esse subvetor menor. Além disso, precisamos comparar o tempo de execução dessa implementação com a versão padrão do Quicksort. Para isso, vamos precisar entender como funcionam ambos os algoritmos e como implementar uma versão híbrida que combina os dois.
Passo 2
Primeiro, vamos entender o Quicksort. Ele é um algoritmo de ordenação eficiente que segue a estratégia “dividir para conquistar”. A ideia principal é:
- Escolher um “pivô”: Um elemento do vetor que vai ajudar a dividir o vetor em partes menores.
- Particionar o vetor: Reorganizar os elementos de tal forma que todos os elementos menores que o pivô fiquem à esquerda e os maiores à direita.
- Recursivamente aplicar Quicksort nas subpartes esquerda e direita até que todo o vetor esteja ordenado.
Vamos implementar uma função básica de Quicksort em Python:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # Escolhendo o pivô como o elemento do meio
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
Passo 3
Agora, vamos falar sobre o Insertion Sort. Este é um algoritmo simples e eficiente para ordenar pequenos vetores. Ele funciona de forma semelhante à maneira como organizamos cartas na mão: pegamos um elemento e o inserimos na posição correta em relação aos já ordenados. Os passos básicos são:
- Percorrer o vetor do segundo elemento ao último.
- Para cada elemento, compará-lo com os anteriores e trocá-lo de posição até que esteja no lugar certo.
Aqui está uma implementação em Python:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# Move os elementos de arr[0..i-1], que são maiores que a chave, para uma posição à frente
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
Passo 4
O próximo passo é combinar Quicksort e Insertion Sort. A ideia é usar Quicksort para dividir o vetor até que os subvetores tenham menos de 10 elementos. Quando isso acontecer, usamos o Insertion Sort para ordenar esses pequenos subvetores, já que o Insertion Sort é mais eficiente para tamanhos pequenos.
Vamos modificar a função de Quicksort para incluir essa lógica:
def hybrid_sort(arr, threshold=10):
if len(arr) <= threshold:
return insertion_sort(arr)
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return hybrid_sort(left, threshold) + middle + hybrid_sort(right, threshold)
Passo 5
Finalmente, vamos comparar o tempo de execução entre a versão padrão do Quicksort e nossa versão híbrida que usa Insertion Sort para subvetores pequenos. Para isso, usaremos a biblioteca
time
do Python para medir o tempo.Aqui está como podemos fazer isso:
import time
import random
# Gerando uma lista aleatória de 10000 elementos
data = random.sample(range(100000), 10000)
# Medindo o tempo do Quicksort padrão
start_time = time.time()
sorted_quicksort = quicksort(data.copy())
quicksort_time = time.time() - start_time
# Medindo o tempo do Quicksort híbrido
start_time = time.time()
sorted_hybrid = hybrid_sort(data.copy())
hybrid_time = time.time() - start_time
print(f"Tempo do Quicksort padrão: {quicksort_time:.4f} segundos")
print(f"Tempo do Quicksort híbrido: {hybrid_time:.4f} segundos")
Resposta
Ao executar o código acima, você verá uma comparação clara dos tempos de execução entre o Quicksort padrão e o Quicksort híbrido que utiliza Insertion Sort para subvetores menores que 10 elementos. Geralmente, a versão híbrida tende a ser mais rápida ou comparável ao Quicksort padrão, especialmente em casos onde muitos subvetores pequenos são criados, aproveitando a eficiência do Insertion Sort nesses cenários.